Salut,
Alors voila, j'ai la fonction factorielle codé comme ca

int factorielle(int n)
{
   return n == 1 ? 1 : n * factorielle(n - 1);
}

Je suppose qu'on ne met jamais d'entier négatif, c'est juste pour l'exemple.
Du point de vue de l'ordinateur, comment il exécute cette fonction ? (les fonctions récursif en général)
Pour moi logiquement, il lit l'instruction, il appelle la fonction factorielle avec l'argument (n-1) etc etc
mais d'après mon prof c'est pas du tout comme ca que ca se passe réellement
malheureusement il n'a pas donné plus d'explication

Ca depend du langage. Dans un langage comme le C, avec un compilateur basique, tu as raison, c'est comme ca que la fonction est execute.

Ici, la fonction est recursive terminale. Donc le compilateur peut faire de la derecursivation et retirer l'appel recursif en transformant en boucle for. Je te laisse le pointeur wikipedia qui va bien: https://en.wikipedia.org/wiki/Tail_call

Alors pour comment l'ordinateur interprète ca on peut pas le savoir en ayant seulement le code, ca dépend entièrement de l’implémentation. A priori l'optimisation d'une fonction récursive finale c'est possible comme le dit mon vdd, pour ca essaye de comparer le code compilé avec optimisations de ton bout de code et d'un bout de code similaire utilisant une boucle.

Ou plus simplement, lit l'assembleur directement et voit si il fait un appel recursif ou pas.

Le programme va utiliser une zone mémoire qui lui est réservé la pile d’exécution ou stack en anglais. Quand il va lire factorielle (n-1) il va empiler dans cette zone l'adresse de retour de la fonction courante et puis appeler factorielle (n-1) et ainsi de suite jusqu'à ce qu'il renvoie 1. A ce moment là il va dépiler l'adresse de retour de la fonction précédente, multiplier le résultat, puis dépiler l'adresse précédente etc. Jusqu'à la première factorielle.

On voit que si la récursivité est trop grande il y a un risque de sur-remplir la pile ce qui ferait planter le programme. Une autre façon de faire c'est la récursivité terminale. Par exemple ici la fonction factorielle récursive terminale : à chaque appel il n'y a pas besoin d'empiler l'adresser de retour car il n'y a plus rien à calculer dans la fonction courante.

int factorielle(int n, int a)
{
   return (n == 0) ? a : factorielle(n-1,a*n);
}

Le 28 janvier 2019 à 01:57:14 godrik a écrit :
Ca depend du langage. Dans un langage comme le C, avec un compilateur basique, tu as raison, c'est comme ca que la fonction est execute.

Ici, la fonction est recursive terminale. Donc le compilateur peut faire de la derecursivation et retirer l'appel recursif en transformant en boucle for. Je te laisse le pointeur wikipedia qui va bien: https://en.wikipedia.org/wiki/Tail_call

La fonction de l'auteur est non terminale, celle de ]Mewtwo[ l'est.

multiplication est associative, le compilateur devrait savoir faire la transformation.

J'ai jamais essaye en C, mais un compilateur lisp d'il y a 15 ans savait faire la transformation.