7 réponses
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
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) :
Comme on connait factorielle 0 on peut remonter la pile des appels
On a dû mémoriser la suite d'appel ce qui est mauvais car ici on pouvait mieux faire :
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
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
Je ne vois pas trop ton histoire d'algorithme récursif branch & bound dans un arbre. En revanche, beaucoup d'algorithmes ont une version naturelle et simple sous forme récursive. Quelques exemples :
*) le DFS (recherche en profondeur dans gaphe) s'exprime très simplement de la sorte ;
*) l'algorithme de tri le plus implémenté (quicksort) est récursif (la version itérative est d'implémentation compliquée). Un des algorithmes par comparaisons les plus rapides, asymptotiquement en tout cas, (le tri fusion) est récursif ;
*) la FFT ou encore Karatsuba pour la multiplication de grans entiers sont récursifs.
Calaz
*) le DFS (recherche en profondeur dans gaphe) s'exprime très simplement de la sorte ;
*) l'algorithme de tri le plus implémenté (quicksort) est récursif (la version itérative est d'implémentation compliquée). Un des algorithmes par comparaisons les plus rapides, asymptotiquement en tout cas, (le tri fusion) est récursif ;
*) la FFT ou encore Karatsuba pour la multiplication de grans entiers sont récursifs.
Calaz
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
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...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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
* 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
