Une fonction récursive est une fonction qui s'appelle elle-même.

Un exemple simple : la définition d'une suite définie par récurrence.

On aimerait définir une suite par son premier terme \(u_0 = 2 \) et la formule de passage d'un terme au suivant : \( u_{n} = 3 * u_{n-1} \), ou plus généralement \( u_n = f\left( u_{n-1} \right) \) où \( f\) est une fonction.

Calcul itératif

Pour calculer \(u_3\) par exemple, on calcule \(u_1 = f(u_0)\) puis \(u_2 = f(u_1) \) et enfin \( u_3 = f(u_2) \).

Cette présentation mène assez naturellement à cette programmation :

def f(x):
	return 3*x
	
	
def u(n):
	terme = 2
	for i in range(1, n+1):
		terme = f(terme)
	return terme
	
	
print(u(3))

Programmation récursive

Mais on peut également programmer le calcul des termes de cette suite en calquant sa définition par récurrence :

def f(x):
	return 3*x
	
	
def u(n):
	if n == 0:
		return 2
	else:
		return f(u(n-1))
	
	
	
print(u(3))

Schématiquement, le déroulement est le suivant :

Programmer des deux façons précédentes le calcul du terme u(n) d'une suite définie par ses deux premiers termes \( u_0 = 5 \) et \( u_1 = 7 \) et la formule de passage au terme suivant : \( u_n = 2 \times u_{n-2} + 3 \times u_{n-1}\).

def f(x, y):
	return 2*x + 3*y
	
	
def u(n):
	t0, t1 = 5, 7
	
	for i in range(2, n+1):
		t0, t1 = t1, f(t0, t1)
		
	if n == 0 : return t0
	else: return t1
	
	
	
	
print(u(2))
print(u(3))

def f(x, y):
	return 2*x + 3*y
	
	
def u(n):
	if n == 0:
		return 5
	elif n == 1:
		return 7
	else:
		return f(u(n-2), u(n-1))
	
	
	
print(u(2))
print(u(3))