Programmation récursive

Définition succincte

Une fonction sera dite programmée récursivement lorsqu'elle fait appel à elle-même dans le corps de sa définition.

Afficher pour comprendre.

Le programme qui suit vous propose une fonction définie récursivement. Sa seule utilité est de vous permettre, notamment à l'aide d'affichages, de comprendre le principe.

def compteARebours(n) :
	if n == 0 : pass # pass est une instruction qui "ne fait rien"
	else :
		print(n, end = " ")
		compteARebours(n-1)


compteARebours(5)

Réponse de python :

5 4 3 2 1

L'instruction qui suit le test if n==0 est ce que l'on nomme "le cas de base", c'est ce qui permet de stopper les appels récursifs.

Si l'on oublie le cas de base en écrivant :

def compteARebours(n) :
	print(n, end = " ")
	compteARebours(n-1)


compteARebours(5)

les appels récursifs seront sans fin, ce qui est une erreur de programmation. Dans la pratique, en python, un nombre maximum d'appels récursifs par défaut arrêtera la boucle sur une erreur : "RuntimeError: maximum recursion depth exceeded".

Le cas de base doit être atteint pour jouer son rôle. Dans la première programmation, notre cas de base correspondait à n == 0 .
Si l'appel intial est fait avec l'argument 5, on finira par atteindre ce cas puisque chaque appel récursif fait décroître d'une unité la valeur de l'argument.
Mais si un utilisateur appelle notre fonction avec n = -5, on se retrouve dans le cas d'appels récursifs infinis. Il vaudrait donc mieux programmer notre première fonction ainsi :

def compteARebours(n) :
	if n <= 0 : pass  
	else :
		print(n, end = " ")
		compteARebours(n-1)


compteARebours(5)

Une modification du cas de base change également le résultat. Essayez par exemple ceci :

def compteARebours(n) :
	if n <= -10 : pass 
	else :
		print(n, end = " ")
		compteARebours(n-1)


compteARebours(5)

Afficher pour comprendre (2).

Nous reprenons l'exemple précédent, mais nous aimerions maintenant que le décompte se fasse dans l'ordre croissant. Par exemple compte(5) doit afficher "1 2 3 4 5 ".

Il suffit d'échanger deux lignes du programme précédent pour obtenir cet effet.

Essayez de trouver par vous-même cette modification avant de lire le code ci-dessous.

def compte(n) :
	if n == 0 : pass
	else :
		compte(n-1)
		print(n, end = " ")
		
compte(5)

Réponse de python :

1 2 3 4 5 

Le principe est le suivant :

1. Appel : compte(5).
2. Dans l'exécution de compte(5), la fonction compte est appelée avec l'argument 4.
3. On exécute donc compte(4). Dans cette exécution, on appelle compte avec la valeur 3 pour le paramètre.
4. On exécute donc compte(3). Dans cette exécution, on appelle compte avec la valeur 2 pour le paramètre.
5. On exécute donc compte(2). Dans cette exécution, on appelle compte avec la valeur 1 pour le paramètre.
6. On exécute donc compte(1). Dans cette exécution, on appelle compte avec la valeur 0 pour le paramètre.
7. On exécute donc compte(0). L'exécution de compte(0) ne fait rien (c'est le sens de l'instruction pass).
8. L'exécution de compte(0) est terminée. Mais cette exécution a été lancée depuis l'exécution de compte(1), qui, elle, n'est pas terminée puisqu'il restait une ligne à exécuter : la ligne print(n, end=" "). Cette ligne est donc exécutée : la valeur 1 s'affiche à l'écran.
9. L'exécution de compte(1) est ainsi terminée (il n'y a plus aucune ligne d'instruction à exécuter). Mais cette exécution de compte(1) avait été lancée depuis une exécution de compte(2). Et cette exécution de compte(2) n'est pas terminée : il restait la ligne print(n, end = " ") à exécuter. Elle est donc exécutée, et 2 est donc imprimé à l'écran.
10. L'exécution de compte(2) est ainsi terminée (il n'y a plus aucune ligne d'instruction à exécuter). Mais cette exécution de compte(2) avait été lancée depuis une exécution de compte(3). Et cette exécution de compte(3) n'est pas terminée : il restait la ligne print(n, end = " ") à exécuter. Elle est donc exécutée, et 3 est donc imprimé à l'écran.
11. L'exécution de compte(3) est ainsi terminée (il n'y a plus aucune ligne d'instruction à exécuter). Mais cette exécution de compte(3) avait été lancée depuis une exécution de compte(4). Et cette exécution de compte(4) n'est pas terminée : il restait la ligne print(n, end = " ") à exécuter. Elle est donc exécutée, et 4 est donc imprimé à l'écran.
12. L'exécution de compte(4) est ainsi terminée (il n'y a plus aucune ligne d'instruction à exécuter). Mais cette exécution de compte(4) avait été lancée depuis une exécution de compte(5). Et cette exécution de compte(5) n'est pas terminée : il restait la ligne print(n, end = " ") à exécuter. Elle est donc exécutée, et 5 est donc imprimé à l'écran.
13. L'exécution de compte(5) est donc terminée.

Une somme.

L'exemple suivant calcule la somme des entiers 1 + 2 + 3 + ... + n.

Cherchez à comprendre son déroulement.

def somme(n) :
	if n == 0 : return 0
	else :
		return n + somme(n-1)
		
print(somme(5))

Réponse de python :

15

Le principe est le suivant :

1. Appel : somme(5).
2. somme(5) doit retourner 5 + somme(4). Mais somme(4) n'est pas connu à ce stade.
3. somme est donc exécutée avec l'argument 4 pour évaluer somme(4). somme(4) doit retourner 4 + somme(3). Mais somme(3) n'est pas connu à ce stade.
4. somme est donc exécutée avec l'argument 3 pour évaluer somme(3). somme(3) doit retourner 3 + somme(2). Mais somme(2) n'est pas connu à ce stade.
5. somme est donc exécutée avec l'argument 2 pour évaluer somme(2). somme(2) doit retourner 2 + somme(1). Mais somme(1) n'est pas connu à ce stade.
6. somme est donc exécutée avec l'argument 1 pour évaluer somme(1). somme(1) doit retourner 1 + somme(0). Mais somme(0) n'est pas connu à ce stade.
7. somme est donc exécutée avec l'argument 0 pour évaluer somme(0). somme(0) retourne la valeur 0.
8. somme(0) étant maintenant connue, on peut terminer l'évaluation de somme(1) : somme(1) = 1 + somme(0) = 1 + 0 = 1.
9. somme(1) étant maintenant connue, on peut terminer l'évaluation de somme(2) : somme(2) = 2 + somme(1) = 2 + 1 = 3.
10. somme(2) étant maintenant connue, on peut terminer l'évaluation de somme(3) : somme(3) = 3 + somme(2) = 3 + 3 = 6.
11. somme(3) étant maintenant connue, on peut terminer l'évaluation de somme(4) : somme(4) = 4 + somme(3) = 4 + 6 = 10.
12. somme(4) étant maintenant connue, on peut terminer l'évaluation de somme(5) : somme(5) = 5 + somme(4) = 5 + 10 = 15.

Dans cette page, vous pouvez coller le code de la fonction python et visualiser pas à pas son exécution.

Afficher pour comprendre (3).

Nous compliquons (un peu artificiellement !) l'exemple précédent du compte à rebours avec des valeurs de retour pour la fonction. Le but est de décomposer cet exemple pour bien saisir le déroulement des appels récursifs.

def d(n) :
	if n == 0 :
		return 1
	else :
		print(n)
		y = d(n-1)
		return 5*y


n = 3		
print( "Valeur de d({}) : {}.".format(n, d(n)) )

Réponse de python :

3
2
1
Valeur de d(3) : 125.

Schématisons le déroulement pour tenter de mieux saisir le fonctionnement.

Tout d'abord, la 'descente'.

Un premier appel de la fonction d avec l'argument 3 :

Lors de cette exécution de d(3), un appel à d avec l'argument 2 a lieu :

Dans cette exécution de d(2), un appel à d avec l'argument 1 a lieu :

Lors de l'exécution de d(1), un appel à d avec l'argument 0 a lieu :

Ensuite, on 'remonte' :

La dernière étape se fait en-dehors de la fonction :
print( "Valeur de d({}) : {}.".format(n, d(n)) ) affiche la valeur de d(3), c'est à dire 125.

Afficher pour comprendre (4).

On présente une petite variante du programme précédent.
Seules deux lignes sont interverties dans le programme par rapport au précédent.
Chercher à analyser ce que sera l'affichage avant de tester le programme.

def c(n) :
	if n == 0 :
		return 1
	else :
		y = c(n-1)
		print(n)
		return 5*y


n = 3		
print( "Valeur de c({}) : {}.".format(n, c(n)) )

Réponse de python :

1
2
3
Valeur de c(3) : 125.

On constate que les affichages intermédiaires (les affichages internes à la fonction) sont inversés par rapport au programme précédent.

Schématisons le déroulement pour tenter de mieux saisir le fonctionnement.

Tout d'abord, la 'descente' :

Ensuite, la 'remontée' :

Et on continue :

On poursuit :

La dernière étape se fait en-dehors de la fonction :
print( "Valeur de c({}) : {}.".format(n, c(n)) ) affiche la valeur de c(3), c'est à dire 125.