Exemples de fonctions récursives

I/ Exemples historiques

1) Ackermann

En 1927, Gabriel Sudan a inventé une fonction récursive à deux variables entières, pour répondre à une question mathématique de David Hilbert.

L'année suivante, Wilhelm Ackermann a publié une fonction similaire mais avec trois variables. Ackermann semble avoir créé cette fonction en 1926.

Par la suite, la « fonction d'Ackermann » a été simplifiée en une fonction à deux variables, que voici :

def A(m,n):
	assert m==int(m) and n==int(n) and m>=0 and n>=0
	if m==0:
		return n+1
	elif n==0:
		return A(m-1,1)
	else:
		return A(m-1,A(m,n-1))

Pour des petites valeurs de m et n, le nombre d'appels récursifs de A(m,n) est énorme et le calcul de A(m,n) peut prendre un temps rédhibitoire. Par exemple en calculant A(4,3) on a typiquement

RuntimeError: maximum recursion depth exceeded while calling a Python object

2) McCarthy

C'est en 1970 que John McCarthy a publié sa fonction 91, dont voici la version Python :

def M91(n):
    assert type(n)==int and n>=0
    if n>100:
        return n-10
    else:
        return M91(M91(n+11))

La représentation graphique de cette suite laisse conjecturer que pour n ≤ 100, M91(n)==91 (d'où le nom de la fonction) :

McCarthy a inventé cette fonction pour lancer un défi : prouver que la fonction est constante pour n ≤ 101. La suite de McCarthy est A103847.

II/ Douglas Hofstadter

Douglas Hofstadter, dans son livre, a étudié plusieurs fonctions récursives nommées G, H, F et M, et finalement Q.

1) La fonction G

def G(n):
	assert n==int(n) and n>=0
	if n==0:
		return 0
	else:
		return n-G(G(n-1))

Hofstadter trouve un moyen de dessiner la fonction G sous la forme d'un arbre : pour toute valeur de n, on relie les nœuds n et G(n) par une arête (on dit que n est le parent de G(n)) :

La fonction G est A005206. Le quotient de deux termes successifs de la suite tend vers la solution positive de l'équation x²+x-1=0 (environ 0,618).

2) La fonction H

def H(n):
	assert n==int(n) and n>=0
	if n==0:
		return 0
	else:
		return n-H(H(H(n-1)))

L'arbre de H a aussi une allure fractale :

La fonction H est A005374. Le quotient de deux termes successifs de la suite tend vers la solution de l'équation x³+x-1=0 (environ 0,682).

3) Les fonctions F et M

F comme femelle et M comme mâle. Ces deux fonctions font l'objet d'une récurrence croisée.

a) La fonction F

def F(n):
	assert n==int(n) and n>=0
	if n==0:
		return 1
	else:
		return n-M(F(n-1))

La fonction F est A005378. Pour construire son arbre, on a besoin de la fonction M ci-dessous :

b) La fonction M

def M(n):
	assert n==int(n) and n>=0
	if n==0:
		return 0
	else:
		return n-F(M(n-1))

La fonction M est A005379. Pour construire son arbre, on a besoin de la fonction F ci-dessus :

4) La fonction Q

def Q(n):
	assert n==int(n) and n>=1
	if n<=2:
		return 1
	else:
		return Q(n-Q(n-1))+Q(n-Q(n-2))

La fonction Q (qui n'est pas définie en 0) est A005185. On ne sait pas à l'heure actuelle si Q est définie pour tous les entiers à partir de 1. Hofstadter la décrit comme chaotique. Voici son arbre :

III/ John Conway

La fonction notée a s'appelle fonction à 10 000 $ de Conway.

def a(n):
	assert n==int(n) and n>=1
	if n<=2:
		return 1
	else:
		return a(a(n-1))+a(n-a(n-1))

Il s'agit de la suite A004001 sur l'OEIS (encyclopédie de Conway et Sloane). Conway a présenté cette fonction le 15 juillet 1988 et a promis 10 000 $ au premier qui trouverait une valeur de a(n) qui soit proche de n/2. Douglas Hofstadter dit avoir inventé cette fonction des années auparavant. Voici son arbre :

Pour étudier la fonction de Conway-Hofstadter, il est nécessaire de dérécursifier la fonction, qui, sous sa forme récursive, est trop longue à calculer. Par exemple avec ce script :

N = 65
X = list(range(N))
Y = [0,1,1]
for n in range(3,N):
    Y.append(Y[Y[n-1]]+Y[n-Y[n-1]])
plot(X,Y,'b-o')

on obtient ce graphique :

Conway a prouvé que a(n)≥n/2, d'où l'idée de représenter la différence :

Z = [Y[k]-X[k]/2 for k in range(len(X))]
plot(X,Z,'b-o')

ce qui donne

et on peut dézoomer :