Récursivité ne fonctionne pas comme voulu

Question

J'ai un tableau et je veux remplir ce tableau en utilisant la récursivité. Il s'agit de la séquence de Collatz. Il n'est pas nécessaire de connaître le problème pour comprendre le code. Le code que je l'ai écrit est le

suivant

int recursion(long int n, int *array){ 
    if(*(array + n)==0){//check if I already have the length of the sequence for this n 
     if((n+1)/2==(double)(n+1)/(double)2){//check if n mod 2 == 0 
      *(array+n) =recursion((n+1)/2-1,array)+1; 
     }  
     else{ 
      *(array +n)=recursion(3*n+3,array)+1; 
     } 
    } 
    else{ 
     return *(array+n); 
    } 
} 

L'idée est que si j'ai un tableau avec des zéros sauf ce tableau [0] = 1 et si j'écris recursion(100,array) alors la fonction vérifie si à la position 100 du tableau est zéro. Si c'est zéro, alors la fonction vérifie une autre condition et assigne un nombre au tableau [100]. Ce tableau [100] est défini de manière récursive. Si finalement il voit un élément de tableau qui n'est pas zéro, il retourne cet élément de tableau.

Je m'attends à ce que dans ce processus de récursivité pour n = 100, non seulement trouver une valeur pour array [100], mais aussi pour d'autres éléments de tableau. Mais si j'exécute cette fonction dans ma fonction principale, cela donne pour plusieurs éléments de tableau un 1 et pour array [100] c'est aussi 1, mais devrait être beaucoup plus grand que 1, puisque j'ajoute 1 dans chaque récursion. Je ne vois vraiment pas ce que je néglige ici.

Answer 1

1. Puisqu'il n'y a pas de code qui crée le tableau, êtes-vous sûr que 3 * n + 3 est inférieur à la longueur du tableau?

2. vous attribuez les valeurs des éléments de retour de la fonction:

*(array +n)=recursion(3*n+3,array)+1;

mais votre fonction ne renvoie pas toujours une valeur. C est très étrange de ne pas exiger de vérifier s'il est en fait une déclaration de retour, et dans ce compilateur cas devine ou quelque chose ...

Pour gcc, compiler avec -Wreturn-type, il vous donnera un avertissement:

a.c: In function ‘recursion’: 
a.c:16:1: warning: control reaches end of non-void function [-Wreturn-type] 

3. Je suis un peu confus de votre texte. Vous savez que array [100] est un 101ème élément du tableau et non 100-ème, n'est-ce pas?

si, en supposant que n représente un index dans la matrice (qui commence par 0) et Collatz est pour les nombres positifs (en commençant par 1) devrait-il pas:

if((n+1) % 2 == 0) { 
    // this was right one 
    array[n] = recursion ((n+1)/2 - 1, array) + 1; 
} else { 
    // this one was probably wrong 
    array[n] = recursion (3 * (n+1) /*+ 1 - 1 */, array) + 1; 
} 

et ensuite appeler recursion(99,array)

Answer 2

Une chose qui ne va vraiment pas: Vous avez un if dans votre fonction, mais vous seulement return une valeur dans l'une des branches. Vous devez changer

else{ 
    return *(array+n); 
} 

à

return *(array+n); 

afin de vous assurer que la fonction retourne toujours une valeur. Par ailleurs, vous pouvez simplement écrire array[n] au lieu de *(array + n).