La répétion d’instructions (cf structures itératives while et for) est
omniprésente dans la résolution de problèmes algorithmiques.
La récursivité, est une autre forme de structure de contrôle pour traiter les données, qu’elle permet parfois de résoudre plus intuitivement.
Définition
Une fonction récursive est une fonction qui s’appelle elle-même, ce qui déclanche un cycle (une répétition). La récursivité permet de résoudre un problème en le réduisant à un ou plusieurs sous-problèmes plus petits de même nature.
Une fonction récursive comprend :
- un (ou plusieurs) cas de base / condition(s) d’arrêt : des situation simples qui pour lesquels il n’y a plus d’appels récursifs ;
- un (ou plusieurs) appel(s) récursif(s) : l’étape qui réduit le problème vers le cas de base.
def fcn_recursive(…) -> …:
if condition_arret:
resultat = cas_de_base
else:
resultat = fcn_recursive(…) #la fonction se rappelle (cycle)
return resultat
Chaque appel a ses propres variables locales et son propre point de reprise.
Le cas de base est indispensable pour éviter les cycles d’appels infinis.
Exemple - factorielle
La factorielle n’un nombre n, notée n! est le produit de ce nombre par
tous les nombres supérieurs à 0 qui le précèdent : n! = n x (n-1) x (n-2) x … x 1 ;
exemple : 4! = 4 x 3 x 2 x 1.
La factorielle se résoud sans difficultés avec une structure itérative for :
def factorielleIte(n: int) -> int:
"""
calcule la factorielle d'un nombre
@param n le nombre dont on veut calculer la factorielle
@return n!
précondition : n ≥ 0
"""
result = 1
for i in range(2, n+1): #on peut commencer à 2 (0! = 1, et 1 x 1 = 1)
result = result * i
return result
print(factorielleIte(4))
La factorielle est un exemple emblématique d’une résolution récursive ; en
effet n! = n x (n-1)! :
def factorielleRec(n: int, trace: int = 0) -> int:
print(" " * trace + "factorielleRec(" + str(n) + ") = ", end="")
if n == 0: #cas de base : 0! = 1
print("1")
resultat = 1
else:
print(str(n) + " x factorielleRec(" + str(n-1) + ")")
resultat = n * factorielleRec(n-1, trace + 1)
return resultat
print(factorielleRec(5))
A chaque appel, si la condition d’arrêt du cas de base n’est pas vérifiée, il y a un appel récursif, dont la fonction appelante attend le résultat.
Remarque : la variable trace et les instructions print de la fonction
n’ont qu’une finalité pédagogique (pour tracer les appels récursifs).
Cette fonction est généralement écrite de façon plus compacte :
def factorielleRec(n: int) -> int:
if n <= 1: #cas de base: 0! = 1! = 1
return 1
else:
return n * factorielleRec(n-1)
ou encore plus simplement :
def factorielleRec(n: int) -> int:
return 1 if n <= 1 else n * factorielleRec(n-1)
Cet exemple illustre le remplacement de la structure itérative for par une
alternative (cas de base) et un appel récursif.
Algorithme itératif qui effectue la somme des éléments d’un tableau :
from typing import List
def sommeIte(tab: List[float]) -> float:
total = 0
for v in tab:
total += v
return total
print(sommeIte([2, 4, 7, 12]))
Et sa version récursive :
from typing import List
def sommeRec(tab: List[float]) -> float:
if len(tab) == 0:
return 0
else:
return tab[0] + sommeRec(tab[1:]) #tab[1:] copie tab à partir de l'indice 1
print(sommeRec([2, 4, 7, 12]))
Lorsque l’appel récursif est la dernière instructions de la fonction (comme c’est le cas avec la factorielle), la forme de la récursion est dite terminale. S’il y a récursion terminale, l’algorithme récursif peut être converti en itératif (sans pile) ; c’est ce que font automatiquement certains compilateurs ou interpréteurs.