Une fonction récursive est une fonction qui s'auto-appelle.

 

Cela est utile pour remplacer des boucles « for »  ou « while », soit parce qu’il arrive que cela ne puisse pas fonctionner avec ces boucles, soit pour des raisons de gain de temps d’exécution, ce qui optimise la fonction, comme dans le cas des listes (voir Algorithmes de références > Tris )

 

 

Pour expliquer la récursivité, prenons un exemple simple qui permet de calculer la factorielle de nb : nb ! soit nb ! = nb x nb-1 x nb-2 x … x 1

 

Nous pourrions écrire avec une boucle « while »:

 

def factorielle(nb):
	fact = 1
	i = 1
	while i < nb:
		i = i + 1
		fact = fact * i
	return fact

Cela donnerait pour factorielle(3) :
	fact = 1
	i = 1
	test  (i=1) < (nb=3) : oui > i = 1 + 1 = 2	fact = 2 x 1 = 2
	test  (i=2) < (nb=3) : oui > i = 2 + 1 = 3	fact = 3 x 2 = 6
	test  (i=3) < (nb=3) : non > renvoie 6

 

Nous pourrions écrire avec une récursivité :

 

def factorielle(nb):    
	if nb<2:
		return 1
	else:
		return nb*factorielle(nb-1)

 

Cela donnerait pour factorielle(3) :
		 test  (nb=3) < (2) : non > renvoie 3 x factorielle(2) 
	3   x   (test  (nb=2) < (2) : non renvoie 2 x factorielle(1))
	3 x 2 x (test  (nb=1) < (2) : oui renvoie 1  ) 
	3 x 2 x 1 = 6
					
	

Free Joomla! template by L.THEME