Je ne suis pas capable de comprendre la récurrence des fonctions. Comment ça marche? comment les valeurs sont stockées et tout?

Je ne suis pas capable de comprendre la récurrence des fonctions. Comment ça marche? comment les valeurs sont stockées et tout?

int tree_size(struct node* node) { if (node==NULL) { return(0); } else { return(tree_size(node->left) + tree_size(node->right) + 1); } } 

Lors de la saisie d’une fonction, un nouveau cadre de stack est créé (sur la stack en mémoire). Le cadre de stack assure le suivi des données locales dans cette fonction, telles que les variables définies localement et les arguments entrants. (Et d’autres éléments tels que l’adresse de retour et les valeurs de registre stockées précédemment qui doivent être préservées. Toutefois, cela n’est pas aussi pertinent pour cette question.)

Avec la récursivité, lorsque vous appelez une fonction à partir de la même fonction, vous créez un nouveau cadre de stack (comme pour tout appel) et ce nouveau cadre de stack stockera les variables locales pour le nouvel appel.

Comme l’a souligné C. Stoll, l’ordre des deux appels est indéterminé en raison de l’opérateur +.

considérer les trois suivants

      1
   2 3
  4 5 6
 7

1 a deux enfants (2 et 3) 2 a deux enfants (4 et 5) .. 4 a un enfant (7)
et vous voulez connaître la taille de l’arbre à 1:

 tree_size(tree1); 

Parce que tree1 n’est pas NULL, la condition if n’est pas vraie. L’instruction else sera donc exécutée:

 tree_size(tree1): return tree_size( tree_size(tree2) + tree_size(tree3) + 1 ) 

idem pour tree2 et tree3

 tree_size(tree2): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 ) tree_size(tree3): return tree_size( tree_size(tree6) + tree_size(NULL) + 1 ) 

etc. Maintenant, si nous substituons la valeur de retour de tree_size (tree2) à tree_size (tree3) dans tree_size (tree1), nous aurions:

 tree_size(tree1): return tree_size( tree_size(tree4) + tree_size(tree5) + 1 + tree_size(tree6) + tree_size(NULL) + 1 + 1 ) 

Maintenant, vous pouvez voir le terme 1 + 1 + 1, c’est la taille de l’arbre pour les deux premiers niveaux, si nous continuons à substituer les appels tree_size, nous aurons un nombre de n fois 1, avec n la taille du arbre

Je pense que la ligne qui vous trouble le plus est ..

 return(tree_size(node->left) + tree_size(node->right) + 1); 

Si vous avez appelé cette fonction sur le nœud supérieur, cela vous indiquera que le nombre de nœuds dans l’arborescence est le nombre de nœuds à gauche, plus le nombre à droite, plus le nœud sur lequel vous venez d’appeler la fonction.

Maintenant, je ne pense pas que ce soit la récursion qui vous déroute, si c’est le cas, laissez un commentaire et je peux l’expliquer un peu plus.

Le problème que je pense que vous rencontrez est quel ordre la ligne sera exécutée. Eh bien, il suit les règles de mathématiques logiques pour «addition». Notez que nous soaps que nous n’avons pas à nous préoccuper des surcharges d’opérateurs, car tree_size renvoie un int , nous avons donc

 intA + intB + intC; 

J’espère que je n’ai pas besoin de vous dire que peu importe l’ordre dans lequel vous ajoutez ces trois valeurs, vous obtiendrez le même résultat.

Cependant, l’ordre dans lequel ils sont ajoutés est bien défini. Si vous pensez à l’opérateur + dans sa fonction, ce sera un peu plus clair. Nous avons fondamentalement (et j’espère que j’ai bien compris):

 operator+(intA , operator+( intB, intC); 

Donc, vous voyez, nous devons d’abord calculer B + C avant d’append A, ou si nous revenons à la ligne de code en question, nous obtenons d’abord la tree_size l’ tree_size à droite, puis nous en ajoutons un, puis append sur la tree_size de l’ tree_size de la gauche. C’est une chose importante à prendre en compte, vous pouvez faire quelque chose de très étrange, comme modifier la taille de l’arbre lorsque vous obtenez la valeur … par exemple, si vous déplacez des nœuds d’un côté à l’autre. Bien sûr, ce serait un très mauvais arbre si on ne pouvait pas compter sur sa taille.

Je crains d’avoir un peu trop insisté ici, alors si j’ai un peu manqué le but, laissez un commentaire et je me ferai un plaisir d’aider à améliorer cette réponse pour vous.

L’analogie avec l’utilisation de morceaux de papier (par @nhahtdh dans les commentaires à Q) est très bonne. Laissez-moi élaborer.

Commencez par réécrire votre code de manière plus linéaire:

 int tree_size(struct node* node) { if (node==NULL) { return(0); } else { x = tree_size(node->left); y = tree_size(node->right); z = x + y; r = z + 1; return( r ); } } 

Imaginez que vous ayez devant vous une stack épaisse (pratiquement inépuisable) de feuilles de papier vides. Vous avez également diverses recettes (définitions de fonctions) à gauche de vous sur votre bureau et un espace vide à droite de vous.

Désormais, appeler une fonction signifie copier sa définition de sa recette sur la feuille de papier située au-dessus de la stack de papiers devant vous, puis substituer les valeurs d’argument de l’appel aux parameters de la fonction, et continuer à partir de là.

Lorsque vous frappez une ligne avec un appel de fonction ( marquez un appel de fonction), marquez cette ligne sur la feuille de papier devant vous, déplacez ce papier à droite (face imprimée dessus) et commencez à travailler sur la nouvelle feuille vide de papier devant vous. Copiez-y la recette de la fonction à appeler, notez les valeurs des arguments et poursuivez votre travail conformément à la recette que vous avez devant vous.

Si vous rencontrez un autre appel de fonction, répétez cette séquence d’actions: marquez la ligne devant recevoir le résultat de l’appel de fonction, placez votre feuille de papier actuelle au-dessus de la stack à droite (vers le haut), copiez la nouvelle recette sur la feuille supérieure devant vous et continuez comme avant.

Maintenant, lorsque vous frappez une ligne dans la recette actuelle qui dit return , notez la valeur retournée sur la feuille de papier supérieure dans la stack à votre droite sur la ligne marquée , puis jetez la feuille de papier actuelle devant vous et déplacez retournez la feuille de papier supérieure de la stack de papiers sur la stack de papiers devant vous.

C’est tout. Tout ce dont vous aviez besoin était de deux stacks de feuilles de papier, une devant vous et une autre à votre droite, ainsi que la stack de papiers avec les définitions de fonctions écrites dessus, à votre gauche.

Notez que nous ne nous soucions pas de savoir si la fonction que nous appelons est identique à l’un des appels de fonctions précédents que nous avons effectués ou non Cela fonctionne quand même.