qu'est ce que tu ne comprends pas ?

n! = n (n-1)!

non ?

d'accord, donc on a écrit cette fonction comme ça pour ne pas avoir de boucle infini, est-ce bien ça?  Parce que sinon j'aurai écris à la fin de la fonction "return factorielle (n)" et non "n*return factorielle(n-1)".

Est-ce que le procédé est le même pour toutes les fonctions récursives? En fait je cherche une méthode pour écrire ces fonctions.

ah ben c'est sûr, faut une condition d'arrêt !

comme n! se calcule pour n 1

la condition d'arrêt est

"si n=1 alors retourner 1
...

est-ce que vous voulez pas plutôt dire si n=0 alors retourner 1?

Donc il y doit avoir une fonction d'arrêt pour les fonctions récursives. Mais ce que je ne comprends pas c'est que cette fonction d'arrêt ne marche que si n=0 (ou n=1??) non? Je comprends pas bien la notion d'arrêt ici. Ce que j'ai compris, c'est qu'il s'agissait d'une exception de la fonction factorielle, lorsque n=0.
(je ne sais pas si je suis assez clair dans ce que je dis ^^).

Si j'écris plutôt



Ca passe mieux ? La fonction récursive ici, c'est

ce qui n'est pas clair dans ta tête c'est la notion d'algorithme récursif !

fonction Fact(n : entier) : entier
     si n=1 alors
          Fact 1
     sinon
          Fact   n*Fact(n-1)
     fin si
fin fonction

hmmm auriez-vous d'autres exemples de fonctions récursives ?

qui soient aussi simple que factorielle

si tu ne piges pas celle-ci, qui est la plus simple, cela ne me parait pas nécessaire de compliquer les choses

n'importe quelle suite définie par récurrence comme le suggère Ulmiere

Bonjour,

la récursivité est une technique de programmation. Par exemple pour le factoriel

sans récursivité :
                 int fact(int n) {
                      int res = 1;
                      for (int i=1; i<=n; i++)
                             res = res*i;
                       return res;
                      }

avec récursivité :
           int fact   (int n){
                if (n==0)
                        return 1;
                 else
                       return fact (n -1)*n;
             }

donc la notion de condition d'arrêt est rappelé ici uniquement pour rappeler de ne pas tomber dans le piège de boucle infini? Puisque que ce soit dans les fonctions récursives ou non, on a des conditions d'arrêt.

D'accord pour les suites de récurrences!

salut,
tu peux suivre l'evolution de la pile en ajoutant des print dans ta fonction
Par exemple (programme Xcas en français à mi-chemin entre le pseudo code et le C++)

Factorielle(n):={
  local res;
  afficher("empiler: "+n);
  si n<2 alors
    res:=1
  sinon
    res:=n*Factorielle(n-1)
  fsi
  afficher("depiler: "+res)
  retourne res
}
:;

empiler: 5
empiler: 4
empiler: 3
empiler: 2
empiler: 1
depiler: 1
depiler: 2
depiler: 6
depiler: 24
depiler: 120