Recursivité

la récursivité (d'un mot latin qui veut dire retour) est le
fait pour une fonction ou une procédure de s'appeler soi même.

on va se servir de cette possibilité pour faire itérer un ensemble
de paramètres

par exemple pour factorielle(x)
si x<>1
factorielle=x*factorielle(x-1)

le problème c'est que le système effectue des copies des variables
qui peuvent rapidement saturer le système et que l'utilisateur ne
perçoit pas clairement ce qui se passe

Une fonction est dite récursive lorsqu'elle s'appelle elle-même. Bien entendu pour ne pas qu'elle s'appelle indéfiniment il faut construire une condition d'arrêt sinon le programme va boucler.

Si l'on reprend l'exemple précédent :

factorielle(n)=n*factorielle(n-1) <-- appel recursif
factorielle(0)=1 <-- condition d'arrêt

Il ne faut pas abuser de la récursivité en programmation car outre le fait que c'est souvent moins lisible qu'une bonne vielle boucle itérative, le volume occupé en mémoire de la pile des appels récursifs à une forte tendance à gonfler. En effet pour calculer factorielle(3) :

factorielle(3)=3*factorielle(2)
  factorielle(2)=2*factorielle(1)
    factorielle(1)=1*factorielle(0)
      factorielle(1)=1*1 <-- condition d'arret

Comme on connait factorielle 0 on peut remonter la pile des appels

    factorielle(1)=1
  factorielle(2)=2*1=2
factorielle(3)=3*2=6

On a dû mémoriser la suite d'appel ce qui est mauvais car ici on pouvait mieux faire :

int i,fact=1;
for(i=1;i<=n;++i){
   fact=fact*i; 
  // la seule chose utilisée pour le calcul est le résultat intermediaire (valeur fact)
}
return fact;

La récursivité est employé dans certains cas bien précis : l'exploration d'un arbre (par exemple dans un branch and bound) est sans doute l'exemple le plus représentatif.

Bonne chance

personnellement g étudié cela en premiére année IAG et j'étais comme vous .
la récursivité et une fonction qui appelle elle même donc en faite c presque une boucle(le même principe)donc elle doit avoir une condition d'arrêt .
prend n'importe quel exemple et essayez de l'exécuter à la main et vous allez bien comprendre ;le plus populaire exemple qui utulisent les débutants est le factoriel d'un entier et la puissance d'un nombre .
On utilise surtout la recursivité pour parcourir un arbre.
essayez et si vous n'avez pas encore compris envoyer moi un mail et j'essaierai d'être plus claire la prochaine fois

Pourtant un ca se fait classiquement dans un arbre (cf intelligence artificielle algo min max, recherche opérationnelle branch & bound ou branch & cut). On peut toujours le faire en iteratif mais bonjour la lourdeur de l'algo niveau implementation...

salut je suis en 1ere annee ei, j'ai un projet que je doit faire sur la recursivité, mais j'ai eu un peu de difficulté, le projet demande d'etudier les inconvenients de la recursivité a travers 2 exemples :
* forme generalisé du factoriel :
nvfact(0,k)=k
nvfact(n,k)=nvfact(n-1,k*n)

* polynome d'hermite hn(x) donne par :
h0(x)=1 h1(x)=2x
hn(x)=2x*hn-1(x)-2(n-1)*hn-2(x) pour n>1

j'aimerai bien avoir des informations et des consignes sur ce petit projet s.v.p
a l'attente d'une reponse :d
merci d'avance

bonjour à tous;
est il possible d'avoir des instructions avant le 'si' d'une procédure récursive??
merci d'avance

Oui.