Programmation récursive

Définition succincte

Il est possible d’appeler une fonction f, non depuis le corps d’une fonction g, mais depuis le corps de la fonction f elle-même.

Définition

Une fonction est dite récursive si elle s’appelle elle-même.

Lorsque plusieurs fonctions s’appellent mutuellement, on parle de récursivité croisée.

La notion informatique de récursivité est proche de la notion mathématique de récurrence.

Un exemple pour comprendre

On considère la fonction suivante dont l'objectif est de calculer des puissances de 2 :


def  DeuxPuissance(n) :
    if n == 0 :
        return 1
    else :
		print(n)
		y=DeuxPuissance(n-1)
		return 2*y
n = 3
print("2 puissance {} est {}".format(n,DeuxPuissance(n)))

Réponse de python :

3
2
1
2 puissance 3 est 8

Le cas le plus simple est celui de l’appel DeuxPuissance(0) qui retourne la valeur 1 sans avoir besoin de refaire un appel à la fonction DeuxPuissance.

On peut alors comprendre la valeur retournée par l’appel DeuxPuissance(1) : quand on exécute le corps de la fonction dans un état dans lequel la valeur de \( n \) est 1, on évalue l’expression 2 * DeuxPuissance(n – 1). Comme la valeur de \( n \) est 1, celle de \( n - 1 \) est 0, donc, celle de DeuxPuissance(n – 1) est 1, ainsi, 2 * DeuxPuissance(n – 1) est 2. L’appel DeuxPuissance(1) retourne donc la valeur 2.

De même, l’appel DeuxPuissance(2) retourne la valeur \( 2^2\), l’appel DeuxPuissance(3) retourne la valeur \( 2^3\) soit 8, et ainsi de suite.

Plus généralement, la valeur retournée par l’appel DeuxPuissance(k + 1) est le double de celle retournée par l’appel DeuxPuissance(k). La valeur retournée par l’appel DeuxPuissance(k) est donc \( 2^k\).

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

Tout d'abord, la 'descente'.

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

Profondeur Instructions n=n1 y2 Affichage Valeur retournée
2 Appel de la fonction DeuxPuissance 3 -
1 (n==0) faux 3 -
1 print(n) 3 - 3
1 y= 3

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

Profondeur Instructions n1 y1 n=n2 y2 Affichage Valeur retournée
2 DeuxPuissance(n-1) 3 2 -
2 (n==0) faux 3 2 -
2 print(n) 3 2 - 2
2 y= 3 2

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

Profondeur Instructions n1 y1 n2 y2 n=n3 y3 Affichage Valeur retournée
3 DeuxPuissance(n-1) 3 2 1 -
3 (n==0) faux 3 2 1 -
3 print(n) 3 2 1 - 1
3 y= 3 2 1

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

Profondeur Instructions n1 y1 n2 y2 n3 y3 n=n4 Affichage Valeur retournée
4 DeuxPuissance(n-1) 3 2 1 0
4 (n==0) vrai 3 2 1 0
4 return 1 3 2 1 0 DeuxPuissance(0)=1

Ensuite, on 'remonte' :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
3 sortie de 'DeuxPuissance(0)' 3 2 1 -
3 affectation y=DeuxPuissance(n-1) 3 2 1 1 -
3 return \( 2\times \)y 3 2 1 2 - DeuxPuissance(1)=2
2 sortie de 'DeuxPuissance(1)' 3 2 - - -
2 Affectation y=DeuxPuissance(n-1) 3 2 2 - - -
2 return \( 2\times \)y 3 2 4 - - - DeuxPuissance(2)=4
1 sortie de 'DeuxPuissance(2)' 3 - - - - -
1 Affectation y=DeuxPuissance(n-1) 3 4 - - - - -
1 return \( 2\times \)y 3 8 - - - - - DeuxPuissance(3)=8
0 sortie de 'DeuxPuissance(3)' - - - - - - -

La dernière étape se fait en-dehors de la fonction :
print("2 puissance {} est {}".format(n,DeuxPuissance(n))) 2 puissance 3 est DeuxPuissance(3), c'est à dire 8.

Aucun résultat explicite n'a lieu durant la "descente", les résultats des calculs sont repoussés après les appels à la fonction alors que l'on est passé à un niveau plus profond d'appel. Ceci explique l'inversion des calculs.
Attachez vous à comprendre ce premier programme, vous aurez saisi l'essentiel de ce que vous devez savoir sur les fonctions récursives.

Remarque

ATTENTION Prévoir un cas de base Dans la définition d’une fonction récursive, il faut toujours prévoir au moins un cas de base, comme le cas n == 0 dans la fonction ci-avant, dans lequel la fonction ne s’appelle pas elle-même, sinon elle s’appelle elle-même indéfiniment.

Méthodologie

Le récursif est particulièrement adapté lorsqu’il est appliqué à une structure récursive.

Les listes et les arbres peuvent être vu comme des structures récursives

Une structure est récursive lorsqu’elle est construite à partir d’un nouvel élément et d’une même structure

Le principe général de la récursivité est la décomposition d’un problème à résoudre en sous-problèmes de même nature (de tailles plus réduites) de façon à se ramener progressivement à l’étude de sous-problèmes dont la résolution est triviale.

Voir l'illustration ci-dessous :

  1. Il faut impérativement que les sous-problèmes soient plus simples que le problème initial.
  2. Il faut également être assuré d’obtenir un cas de base après un nombre fini de subdivision.

Un autre exemple 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.
Un troisième exemple suivra, il présentera une légère modification de ce programme, ce qui devrait vous permettre de mieux saisir le détail de fonctionnement des appels.


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


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

Réponse de python :

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

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 :

Profondeur Instructions n=n1 y1 Affichage Valeur retournée
1 Appel de la fonction d 3 -
1 (n==0) faux 3 -
1 print(n) 3 - 3
1 y= 3

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

Profondeur Instructions n1 y1 n=n2 y2 Affichage Valeur retournée
2 d(n-1) 3 2 -
2 (n==0) faux 3 2 -
2 print(n) 3 2 - 2
2 y= 3 2

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

Profondeur Instructions n1 y1 n2 y2 n=n3 y3 Affichage Valeur retournée
3 d(n-1) 3 2 1 -
3 (n==0) faux 3 2 1 -
3 print(n) 3 2 1 - 1
3 y= 3 2 1

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

Profondeur Instructions n1 y1 n2 y2 n3 y3 n=n4 Affichage Valeur retournée
4 d(n-1) 3 2 1 0
4 (n==0) vrai 3 2 1 0
4 return 0 3 2 1 0 d(0)=0

Ensuite, on 'remonte' :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
3 sortie de 'd(0)' 3 2 1 -
3 affectation y=d(n-1) 3 2 1 0 -
3 return y 3 2 1 0 - d(1)=0
2 sortie de 'd(1)' 3 2 - - -
2 Affectation y=d(n-1) 3 2 0 - - -
2 return y 3 2 0 - - - d(2)=0
1 sortie de 'd(2)' 3 - - - - -
1 Affectation y=d(n-1) 3 0 - - - - -
1 return y 3 0 - - - - - d(3)=0
0 sortie de 'd(3)' - - - - - - -

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 0.

Afficher pour comprendre, bis.

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 0
	else :
		y=c(n-1)
		print(n)
		return y


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

Réponse de python :

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

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' :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
1 Appel de la fonction d 3 - - - - - -
1 (n==0) faux 3 - - - - - -
1 y= 3 - - - - -
2 c(n-1) 3 2 - - - -
2 (n==0) faux 3 2 - - - -
2 y= 3 2 - - -
3 c(n-1) 3 2 1 - -
3 (n==0) faux 3 2 1 - -
3 y= 3 2 1 -
4 c(n-1) 3 2 1 0
4 (n==0) vrai 3 2 1 0
4 return 0 3 2 1 0 c(0)=0

Ensuite, la 'remontée' :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
3 sortie de 'c(0)' 3 2 1 -
3 affectation y=c(n-1) 3 2 1 0 -
3 print(n) 3 2 1 0 - 1
3 return y 3 2 1 0 - c(1)=0

Et on continue :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
2 sortie de 'c(1)' 3 2 - - -
2 Affectation y=c(n-1) 3 2 0 - - -
2 print(n) 3 2 0 - - - 2
2 return y 3 2 0 - - - c(2)=0

On poursuit :

Profondeur Instructions n1 y1 n2 y2 n3 y3 n4 Affichage Valeur retournée
1 sortie de 'c(2)' 3 - - - - -
1 Affectation y=c(n-1) 3 0 - - - - -
1 print(n) 3 0 - - - - - 3
1 return y 3 0 - - - - - c(3)=0
0 sortie de 'c(3)' - - - - - - -

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 0.

Aucun affichage n'a lieu durant la "descente", les affichages sont repoussés après les appels à la fonction alors que l'on est passé à un niveau plus profond d'appel. Ceci explique l'inversion des affichages.
Attachez vous à comprendre ces trois programmes, vous aurez saisi l'essentiel de ce que vous devez savoir sur les fonctions récursives.