Soit la liste définie par la relation de récurence suivante :
Un = 3 Un-1 - 2
U0 = 2
|
/* La fonction suite calcule
le n ième élément de la suite */
|
|
| Algorithme itératif | Algorithme récursif |
| res <== 2 | si n = 0 |
| Répéter pour i allant de 1à n | alors rendre 2 |
| res <== 3 * res - 2 | sinon rendre (3 * suite(n-1) -2) |
| fin_de_répéter | |
| rendre (res) | |
| Définition itérative | Définition récursive |
| n ! = 1 *2 *3 *..... *n | n! = n * (n-1)! |
| 1! = 1 |
|
/* La fonction fact calcule
n! */
|
|
| Algorithme itératif | Algorithme récursif |
| res <== 1 | si n = 1 |
| Répéter pour i allant de 2 à n | alors rendre 1 |
| res <== res *i | sinon rendre (n * fact(n-1)) |
| fin_de_répéter | |
| rendre (res) | |
| Définition récursive | |
| fib(n) = fib(n-1) + fib(n-2) | |
| fib(0) = fib(1) = 1 |
| /* La fonction
fib calcule fib(n) */ |
|
| Algorithme itératif | Algorithme récursif |
| AvDernier <== 1 | si n = 0 OU n = 1 |
| Dernier <== 1 | alors rendre 1 |
| Répéter pour i allant de 2 à n | sinon rendre (fib(n-1) + fib(n-2)) |
| Nouveau <== Dernier + AvDernier | |
| AvDernier <== Dernier | |
| Dernier <== Nouveau | |
| fin_de_répéter | |
| rendre (Nouveau) | |
Les classiques coefficients dits du binôme peuvent se calculer essentielement de deux différentes manières.
| Définition "itérative" | Définition récursive |
| Cn,p = n!/(p! * (n-p)!) | Cn,p = Cn-1,p-1 + Cn-1,p |
| Cn,n = 1 | |
| Cn,0 = 1 |
Ne pas oublier que la fonction fact ci-dessous cache soit une boucle soit une définition récursive.
|
/* La fonction binome calcule
le Cn,p*/
|
|
| Algorithme "itératif" | Algorithme récursif |
| rendre (fact(n) / (fact(p) * fact(n-p)) | si n = p ou p = 0 |
| alors rendre 1 | |
| sinon rendre binome(n-1,p-1) + binome(n-1,p) | |
Le probleme dit des tours de Hanoļ est le suivant :
|
/* La procédure Hanoi(N,depart,
arriv, inter) déplace N rondelles du poteau depart au
poteau arriv en utilisant le poteau inter comme poteau intermédiaire*/
|
| Initialiser le poteau dep avec les N rondelles dans le bon ordre |
| si N > 0 |
| alors |
| déplacer N-1 rondelles depuis dep vers inter en utilisant arriv |
| déplacer 1 rondelle depuis dep vers arriv |
|
déplacer N-1 rondelles depuis inter vers arriv en utilisant dep |