Récursivité
Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème.
L’approche récursive est un des concepts de base en informatique.
Les premiers langages de programmation qui ont autorisé l’emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité.
Algorithme itératif vs récursif
On oppose généralement les algorithmes récursifs aux algorithmes itératifs
Alors qu’un algorithme récursif s’exécutent en appeler explicitement l’algorithme lui-même, l’algorithme itératif utilise plutôt des boucles pour et des boucles tant que, pour répéter des opérations.
Exemple de problème : compter des billes sur un tas
Approche itérative
- Initialiser un compteur
- Tant qu’il y a des billes sur le tas
- Incrémenter de 1 le compteur
- Ôter une bille du tas
- Le compteur vaut le nombre de billes
Approche récursive
- Nombre de billes dans le tas = 1 + nombre de billes dans le tas diminué de 1 bille
ou bien, en plus détaillé :
- Compter les billes dans un tas
- Si le tas est vide
- renvoyer 0
- Sinon
- renvoyer 1 + Compter les billes dans un tas diminué de 1 bille
Fonctions récursives
Une fonction est qualifiée de récursive si elle s’appelle elle-même.
Par exemple, cette fonction qui permet de calculer \(x^y\) (\(y\) étant supposé > 0) :
def puissance(x, y):
if y > 0 : # Si y > 0 alors …
return x * puissance(x, y-1) # auto appel de la fonction
else : # Sinon …
return 1 # Arrêt de la récursion
print(puissance(3,8))
Structure
Toute fonction récursive doit avoir, grâce à une structure conditionnelle, une condition pour laquelle elle ne s’appelle pas elle-même. Sans cela, elle ne s’arrêterait jamais !
Cette condition s’appelle le cas de base.
Dans l’exemple précédent, le cas de base est la condition y <= 0 .
En pratique Python prévoit une profondeur de récursion maximum (par défaut 1000, mais modifiable), mais l’atteindre provoque une erreur, et surtout témoigne souvent d’une faute de programmation.
A contrario, les cas pour lesquels un appel récursif à lieu sont appelés cas récursifs.
Il existe toujours une façon non récursive de réaliser une fonction donnée.
Lorsque la structure à traiter ou le problème à résoudre apparait clairement récursif (peut être décrit par récurrence), ecrire une fonction sous forme récursive est souvent plus naturel. En revanche, les grandes profondeurs de récursion peuvent solliciter fortement la mémoire et rendre son exécution plus lente.
Exercices
Proposer un algorithme récursif de calcul de la somme de deux entiers naturels a et b en supposant que les seules opérations de base disponibles sont :
- l’ajout de 1 à un entier :
a+= 1 - le retrait de 1 à un entier :
a-=1 - les comparaisons à 0 d’un entier :
a==0,a>0eta<0
Un palindrome est un mot dont les lettres lues de gauche à droite sont les mêmes que celles lues de droite à gauche.
Exemple : les mots « radar » , « elle » , « été » , « ici » sont des palindromes.
