La récursivité encore appelée récurrence en mathématique permet de réaliser des traitements répétitifs particulièrement complexes que les structures itératives classiques ne peuvent aborder facilement. Elle permet de simplifier la structure des programmes. On dit qu'il y'a récursivité lorsque la définition d'un objet fait apparaître l'objet lui-même.
Quelques exemples d'utilisation de la récursivité
Structure de données récursives
Exemple:
- Les listes.
- Les piles.
- Les files.
- Les arbres.
Le raisonnement récursif
Le raisonnement récursif comporte deux phases bien distinctes:
- Une formulation simpliste ou triviale: qui permet d'arrêter les traitements récursif.
- Une formulation récursive: qui permet de poursuivre le traitement, exemple: tant que la condition est vraie on exécute l'action.
Récursivité indirecte
Encore appelée récursivité cachée ou croisée, la récursivité indirecte a lieu lorsqu'une procédure appelle une seconde procédure qui à son tour appelle la première.
Exemples:
f(n) = g(n-1)
g(n) = f(n-1)
La récursivité directe
Ici la procédure s'appelle elle-même, la condition importante dans l'utilisation de la récursivité directe est que les objets engendrés par une définition récursive doivent être fini. Ainsi dans une procédure utilisant la récursivité directe on a deux notions:
- La procédure s'appelle elle-même: on ne commence avec de nouvelle données.
- Il y'a un texte de fin ou une condition d'arrêt: la procédure doit contenir une construction telle que dans certains cas l'évolution puisse se faire directement sans appel récursif. Pour cela il est souvent préférable d'indiquer le test de fin des appels récursifs en début de procédure. On a donc la formulation suivante:
Premier cas:
si condition_fin alors
instruction
sinon
appel récursif
fin si
Deuxième cas:
tant que non(condition_fin) faire
appel récursif
fin tant que
instruction
Application
Fonction factorielle
La factorielle d'un nombre entier n est le produit des nombres entiers inférieurs ou égaux à ce nombre n. Cette définition peut se noter de plusieurs façons
- 0!=1
1!=1
2!=2
3!=3x2x1
N!=N(N-1)x...x2x1 - N!=1 si N=0
N!=N(N-1)x...x2x1 si N>0 - N!=1 si N=0
N!=N(N-1)! si N>0
fonction factorielle(N:entier):entier
var p, i: entier
début
si N=0 alors
factorielle ←1
sinon
p ← 1
pour i=1 à N faire
p ← i*P
fin pour
factorielle ← p
fin si
fin
Autre fonction
fonction factorielle(N: entier): entier
debut
si N=0 alors
factorielle ← 1
sinon
factorielle ← n*factorielle(n-1)
fin si
fin
Exécution
|
F0 |
F1 |
F2 |
F3 |
F4 |
|
N = 3 |
3*fact(2) |
2*fact(1) |
1*fact(0) |
1 |
Fonction de Fibonacci
f0 ; f1=1
fn=fn-2+fn-1 si n>1
f(n)=n si n<=1
f(n)=f(n-2)+f(n-1) si n>1
Correction:
fonction fibonacci(n:entier):entier
début
si n<=1 alors
fibonacci ← n
sinon← fibonacci(n-1)+fibonacci(n-2)
fin si
fin
Probatoire A-ABI 2021 Epreuve de littérature ou de culture générale