1-02. Récursivité

Fonction appelant une autre fonction

			
			def f(x):
				return 2*x + 1

			def g(x):
				return 2 + f(x)
			
			def h(x):
				return f(x/2)
			
		

Il est possible d’utiliser une fonction à l’intérieur d’une autre fonction – bon, j’espère que ça n’est pas un scoop pour vous.

Plus intéressant, en revanche, il est possible d’écrire une fonction qui s’appelle elle-même. Une sorte de mise en abyme algorithmique.

Fonction s’appelant elle-même

			def f(x):
				if x == 5: return "OK"
				else: return f(5)
		

Bien entendu, la fonction de l’exemple précédent n’a aucun intérêt. Elle sert juste à vous montrer qu’une fonction peut s’appeler elle-même. Et ça, ça nous ouvre de nouveaux horizons !😎

Définition

			
				def f(x):
					print(x) # rappel de la valeur de x
					if x <= 1: return 1 # cas de base
					else: return 1 + f(x-1) # appel d’une valeur plus petite
		
				print( f"f(4) = {f(4)}")
			
		

Arbre d’appels

Reprenons l’exemple de la fonction f(x) vue dans l’activité précédente. À chaque fois que la variable entière x est strictement supérieure à 1, la fonction s’appelle elle-même avec f(x-1). Cet appel s’appelle un appel récursif. Par contre, lorsque x est égal à 1, la fonction renvoie 1. On peut alors représenter l’exécution de f(4) de la façon suivante :

Cette façon de représenter l’exécution d’un programme s’appelle un arbre d’appels. On constate que pour calculer la valeur renvoyée par f(4), il faut d’abord appeler f(3) qui va lui-même déclencher un appel à f(2), qui lui-même appelle f(1) qui enfin renvoie 1. Après ce renvoi de la valeur 1, l’arbre d’appel devient :

L’appel à f(2) renvoie alors 2 et l’arbre d’appel devient :

L’appel f(3) finit alors de s’exécuter pour donner :

Je vous l’accorde ! ☺️ Cette fonction ne fait rien d’intéressant. Elle renvoie simplement x. Mais il faut toujours des cas simples pour mieux saisir les subtilités sous-jacentes. Et ce n’est pas fini. Maintenant qu’on a présenté la notion d’arbre d’appels, nous allon svoir ce qu’est la pile d’exécution.

Pile d’exécution

On donne ci-dessous un programme et son affichage obtenu dans la console lors de son exécution.

		
			def fA():
				print("Début fA")
				i = 0
				while  i < 5:
					print("fA", i)
					i = i + 1
				print("Fin fA")
			
			def fB():
				print("Début fB")
				i = 0
				while  i < 5:
					if  i == 3 :
						fA()
						print("Retour à fB")
					print("fB", i)
					i = i + 1
				print("Fin fB")
			
			fB()

			# Affichage dans la console:
			# Début fB
			# fB 0
			# fB 1
			# fB 2
			# Début fA
			# fA 0
			# fA 1
			# fA 2
			# fA 3
			# fA 4
			# Fin fA
			# Retour à fB
			# fB 3
			# fB 4
			# Fin fB
		
	

Dans cet exemple, la fonction fB appelle une autre fonction fA. La principale chose à retenir de cet exemple est que l’exécution de fB est interrompue pendant l’exécution de fA. Une fois l’exécution de fA terminée, l’exécution de fB reprend là où elle avait été interrompue.

Pour gérer ces fonctions qui appellent d’autres fonctions, le système utilise une pile d’exécution. Une pile d’exécution permet d’enregistrer des informations sur les fonctions en cours d’exécution dans un programme. On parle de pile, car les exécutions successives « s’empilent » les unes sur les autres. Si on s’intéresse la pile d’exécution du programme étudié ci-dessus, on obtient le schéma suivant :

1. appel de la fonction fB qui est ajoutée à la pile d’exécution du programme
2. dans la fonction fB, la fonction fA est appelée, on ajoute cet appel à la pile d’exécution,
3. la fonction fA a fini d’être exécutée, elle est donc dépilée de la pile d’exécution, la fonction fB termine son exécution.

C’est la fonction située au sommet de la pile d’exécution qui est en cours d’exécution. Toutes les fonctions situées en-dessous sont mises en pause jusqu’au moment où elles se retrouvent au sommet de la pile. Quand une fonction termine son exécution, elle est automatiquement retirée du sommet de la pile (on dit que la fonction est dépilée).

Les variables sont associées à la fonction dans lesquelles elles sont définies. C’est le scope (la portée) de la variable. Ici nous avons une variable i dans la fonction fA et une variable i dans la fonction fB. La pile d’exécution garde en mémoire la valeur des variables internes à chaque fonction. C’est ce qui permet de conserver la valeur de i référencée dans fB quand fA est exécutée : ainsi on reprend bien l’exécution de fB avec i qui vaut 3.

L’instruction f(4) (on parle ici de la fonction récursive vue dans la précédente activité) produit les étapes suivantes d’empilement et dépilement dans la pile d’exécution :

Cas de base

Il y a une précaution importante à prendre, avec les fonctions récursives. Il faut s’assurer que le cas de base est toujours atteint. Sinon, la récursion est infinie (et votre script plantera).

Dans la pratique, la profondeur de récursion possible est limitée – tout simplement parce que la mémoire de votre ordinateur est elle-même limitée.

			def f(x):
				if x == 1: return 1
				else: return 1 + f(x-2)
				
			def g(x):
				if x == 0: return 0
				elif x > 0: return g(x+1)
				else: return g(x-1)
				
			def h(x):
				if x <= 10: return "cas de base atteint"
				else: return "x " + h(x-1)
		

Un exemple classique de l’utilisation de la récursivité.

				def factorielle(x):
					if not isinstance(x, int) or x < 0: return "impossible"
					if x <= 1: return 1
					return x*factorielle(x-1)
			

La récursivité n’est pas toujours la meilleure solution.

			def fibonacci_iteratif(n):
				# Cas de base
				if n <= 0: return 0
				if n == 1: return 1
					
				# Initialisation des deux premiers termes
				fib_prev = 0
				fib_current = 1
				
				# Calcul itératif des termes suivants
				for i in range(2, n + 1):
					# Calcul du terme suivant
					fib_next = fib_prev + fib_current
					
					# Mise à jour des valeurs pour l'itération suivante
					fib_prev = fib_current
					fib_current = fib_next
					
				return fib_current
		

				def fibo_rec(x):
					if x <= 1: return x
					return fibo_rec(x-1) + fibo_rec(x-2)