![\"What](\"https://qph.fs.quoracdn.net/main-qimg-a72870f39de7fb8a584832db420b3e29.webp\")
Nous venons de voir des généralités sur les fonctions. Maintenant, nous allons aborder un cas particulier sur celle-ci, les fonctions récursives.
Il s’agit à la fois d’un style de programmation mais également d’une technique pour définir des concepts et résoudre certains problèmes qu’il n’est parfois pas facile de traiter en programmant uniquement avec des boucles.
Pour définir la somme des n premiers entiers, on a l'habitude d’écrire la formule suivante :
0+1+2+...+n-1 + n (1)
Une solution pour calculer cette somme consiste à utiliser une boucle for pour parcourir tous les entiers i entre 0 et n, en s’aidant d’une variable locale s pour accumuler la somme des entiers de 0 à i. On obtient par exemple le code Python suivant :
def somme1(n) :
s = 0
for i in range(n + 1):
s=s+i
return s
print(somme1(5))
La fonction somme(n) ci-dessus calcule bien la somme des n premiers entiers. Cependant, ce code Python n'est pas directement lié à la formule
0+1+2+...+n-1 + n.
En effet, il n’y a rien dans cette formule qui puisse laisser deviner qu’une variable intermédiaire s est nécessaire pour calculer cette somme.
Mettre le résultat ici (code et figure).
Il existe une autre manière d'aborder ce problème. Il s’agit de définir une fonction somme(n) qui, pour tout entier naturel n,donne la somme des n premiers entiers de la manière suivante :
{ 0 si n=0 ,
somme(n) = {
{ n+somme(n-1) si n>0.
Cette définition nous indique ce que vaut somme(n) pour un entier n quelconque, selon que n soit égal à 0 ou strictement positif (n>0).
Ainsi, pour n = 0, la valeur de somme(0) est simplement 0.
Dans le cas où n est strictement positif (n>0), la valeur de somme(n) est n + somme(n - 1).
Par exemple, voici ci-dessous les valeurs de somme(n), pour n valant 0, 1,2,3,4 et 5.
somme(0) = 0
somme(1) = 1+somme(0) = 1+0 = 1
somme(2) = 2+somme(1) = 2+1 = 3
somme(3) = 3+somme(2) = 3+3 = 6
somme(4) = 4+somme(3) = 4+6 = 10
somme(5) = 5+somme(4) = 5+10 = 15
Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n - 1). Il s’agit là d’une définition fonction récursive, c’est-à-dire d’une définition de fonction qui fait appel à elle-même.
Ainsi, pour connaître la valeur de somme(n), il faut connaître la valeur de somme(n - 1), donc connaître la valeur de somme(n - 2), etc. Ceci jusqu’à la valeur de somme(0) qui vaut 0. La valeur de somme(n) s'obtient en ajoutant toutes ces valeurs.
Cette définition récursive de la fonction somme(n) est facilement programmable en Python :
def somme(n) :
if n == 0 :
return 0
else :
return n + somme(n - 1)
print(somme(5))
L'analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle ( if ) pour tester si l’argument n est égal à 0. Si c’est le cas, la
fonction renvoie la valeur 0, sinon elle renvoie la somme de n + somme(n - 1).
Cet appel à somme(n - 1) dans le corps de la fonction est un appel récursif, c'est-à-dire un appel qui fait référence à la fonction que l’on est en train de
définir.
On dit de toute fonction qui contient un appel récursif que c’est une fonction récursive.
Par exemple, l'évaluation de l’appel à somme(5) peut se représenter de la manière suivante :
somme(5) = return 5+somme(4)
|
return 4+somme(3)
|
return 3+somme(2)
|
return 2+somme(1)
|
return 1+somme(0)
|
return 0
return 0
Mettre le résultat ici (code et figure).
Une formulation récursive d’une fonction est toujours constituée de plusieurs cas, parmi lesquels on distingue des cas de base et des cas récursifs
du calcul.
Les cas récursifs sont ceux qui renvoient à la fonction en train d’être définie :
somme(n) = n + somme(n - 1 si n > 0.
Les cas de base de la définition sont à l'inverse ceux pour lesquels on peut obtenir le résultat sans
avoir recours à la fonction définie elle-même :
somme(n) = 0 si n = 0.
Ces cas de base sont habituellement les cas de valeurs particulières pour lesquelles il est facile de déterminer le résultat.
Prenons comme exemple l'opération de puissance
-ième d’un nombre a.
On a donc la multiplication répétée n fois de a avec lui-même.
Cela s'écrit de la manière suivante :
an = a x a x a x ... x a
(_____________)
n fois
avec, par convention a” que la puissance de a pour n = 0 vaut 1.
Pour écrire une version récursive de an, on va créer une fonction puissance(a,n) en réalisant les 2 étapes suivante :
Etape 1 : Rechercher les cas de base
0n a
1 si n = 0
Etape 2 : Déterminer les cas récursifs
On a
a x puissance(a,n-1)
Au final, on obtient définition de la fonction produit(a,n) :
{ 1 si n=0 ,
produit( a , n ) = {
{ a x produit( a , n-1 ) si n>0.
On en déduit le programme suivant de la fonction produit(a,n) :
def produit(a,n) :
if n == 0 :
return 1
else :
return a * produit(a,n-1)
print(produit(2,4))
Mettre le résultat ici (code et figure).
Toute formulation récursive d’une fonction possède au moins un cas de base et un cas récursif. Ceci étant posé, une grande variété de formes est possible.
Cas de base multiples
La définition de la fonction puissance(a,n) n’est
pas unique. On peut par exemple identifier deux cas de base « faciles », celui pour n = 0 mais également celui pour n = 1 avec puissance(a, 1) = a.
Ce deuxième cas de base a l’avantage d'éviter de faire la multiplication (inutile) a x 1 de la définition précédente. Ainsi, on obtient la définition suivante avec
deux cas de base :
{ 1 si n=0 ,
produit( a , n ) = { a si n=1
{ a x produit( a , n-1 ) si n>0.
Cas récursifs multiples
Il est également possible de définir une fonction
avec plusieurs cas récursifs. Par exemple, on peut donner une autre définition pour puissance(a,n) en distinguant deux cas récursifs selon la parité de n.
{ 1 si n=0 ,
produit( a , n ) = { carre(puissance(a,n/2)) si n > 0 et n est pair,
{ a x carre(puissance(x,(n —1)/2)) si n > 0 et n est impair
Mettre le résultat ici (code et figure).
Les expressions qui définissent une fonction peuvent
aussi dépendre de plusieurs appels à la fonction en cours de définition.
Par exemple, la fonction fibonacci(n), qui doit son nom au mathématicien Leonardo Fibonacci, est définie récursivement, pour tout entier naturel n, de la manière suivante :
{ 0 si n = 0
fibonacci(n) = { 1 si n = 1
{ fibonacci(n-2)+fibonacci(n-1) si n > 1.
Les occurrences de la fonction en cours de définition peuvent également être imbriquées. Par exemple, la fonction fn(n) ci-dessous, que l’on doit à John McCarthy (informaticien et lauréat du prix
Turing en 1971), est définie avec deux occurrences imbriquées, de la manière suivante :
{ n - 10 si n > 100
fn(n) = {
{ f91( f91(n + 11)) si n ≤ 100.
Il est également possible de définir plusieurs fonctions récursives en même temps, quand ces fonctions
font référence les unes aux autres. On parle alors de définitions récursives mutuelles.
Par exemple, les fonctions a(n) et b(n) ci-dessous, inventées par Douglas Hofstadter (il y fait référence dans son ouvrage Güdel, Escher, Bach : Les
Brins d’une Guirlande Éternelle, pour lequel il a obtenu le prix Pulitzer en 1980), sont définies par récursion mutuelle de la manière suivante :
{ 1 si n = 0
a(n) = {
{ n - b(a(n-1)) si n > 0.
{ 0 si n = 0
b(n) = {
{ n - a(b(n-1)) si n > 0.
Pour écrire une définition récursive correcte, il faut respecter les règles suivantes :
Règle 1 : il faut s’assurer que la récursion va
bien se terminer, c’est-à-dire que l’on va finir par « retomber » sur un cas de base de la définition.
Règle 2 : il faut que les valeurs utilisées pour appeler
la fonction soient toujours dans le domaine de la fonction.
Règle 3 : il convient de vérifier qu’il y a bien une définition pour toutes les valeurs du domaine.
Les techniques de définition récursive peuvent s’appliquer à toute une variété d'objet, et pas
seulement à la définition de fonctions. Nous verrons en particulier aux des structures de données définies récursivement.
Tester et mettre le résultat ici (code et figure).
Une fois que l’on dispose d’une définition récursive pour une fonction, il faut codé la fonction en Python.
Mais il faut faire attention à 2 points :
1. Le domaine mathématique d’une fonction (les valeurs prise par la définition) , n’est pas toujours le même que l’ensemble des valeurs du type Python avec lesquelles elle sera appelée
2. Le choix d’une définition récursive plutôt qu’une autre peut dépendre du modèle d’exécution des fonctions récursives.
Mettre le résultat ici (code et figure).
Prenons l'exemple de somme(n) :
Sa définition est ;
{ 0 si n=0 ,
somme(n) = {
{ n+somme(n-1) si n>0.
est définit pour n≥0 ou n∈[0 ; +∞ [
Sa fonction en python :
def somme(n) :
if n == 0 :
return 0
else :
return n + somme(n - 1)
est définit pour n∈] -∞ ; +∞ [. En effet, n peut être négatif ou positif.
Tester la fonction pour somme( -1 ) et conclure.
"},{"edit":"Mettre le résultat ici (code et figure).
La fonction somm(-1) provoque une erreur d'exécution.
En effet si n<0 (négatif) la fonction boucle à l'infini.
Pour éviter ce comportement, il y a plusieurs solution :
1. Changer le test n==0 par n<=0, mais là on change le domaine de définition.
2. Une autre solution est de restreindre les appels à la fonction somme(n) en ajoutant une instruction assert avec n>=0.
def somme(n) :
assert n>=0 ,\"Erreur : n doit être positif ou nul\"
if n == 0 :
return 0
else :
return n + somme(n - 1)
print(somme(-2))
Tester le code ci-dessous avec n = 5 et n = -2. Conclure.
Cette solution est correcte, mais elle n’est pas encore satisfaisante. En effet, pour tout appel somme(n) avec n >= 0, chaque appel récursif commencera par faire le test associé à l'instruction assert, alors que chaque valeur de n sera toujours positive.
Une solution pour éviter ces tests inutiles est de définir deux fonctions :
def somme_bis(n) :
if n == 0 :
return 0
else :
return n + somme(n - 1)
def somme(n) :
assert n>=0 ,\"Erreur : n doit être positif ou nul\"
return somme_bis(n)
print(somme(-2))
La fonction somme(n) vérifiera une seule fois que
son argument n est positif. Puis, si c’est le cas, elle appellera la fonction somme_bis(n).
Tester avec les 2 fonctions et conclure.
"},{"htm":"","css":"","js":""}],[{"text":"Une partie de l’espace mémoire d’un programme
est organisée sous forme d’une pile où sont stockés les contextes d'exécution de chaque appel de fonction.
SI nous prenons l'exemple de la fonction puissance(x,n) :
def puissance(x, n):
if n == 0 :
return 1
else:
return x * puissance(x, n - 1)
l’organisation de la mémoire au début de l'appel à puissance(7,4) est un emplacement pour la variable x initialisé à 7 et un autre pour n à 4.
| ... | ||
| x | 7 | puissance(7,4) |
| n | 4 | |
L'environnement contient également d’autres valeurs (comme l'emplacement pour la valeur renvoyée par la fonction, la sauvegarde des registres, etc.)
qui sont simplement représentées par des --- dans le schéma ci-dessus.
Le calcul récursif de puissance(7,4) va engendrer une suite d’appels « en cascade » à la fonction puissance, que l’on peut représenter par l’arbre d’appels suivant :
puissance(7,4)=
return 7 * puissance(7,3)
|
return 7 * puissance(7,2)
|
return 7 * puissance(7,1)
|
return 7 * puissance(7,0)
|
return 1
L’organisation de la pile mémoire est de cette forme pour puissance(7,4) :
| x | 7 | puissance(7,4) |
| n | 4 | |
| x | 7 | puissance(7,3) |
| n | 3 | |
| x | 7 | puissance(7,2) |
| n | 2 | |
| x | 7 | puissance(7,1) |
| n | 1 | |
| x | 7 | puissance(7,0) |
| n | 0 |
Juste après le dernier appel à puissance (7,0), la pile contient donc les environnements d'exécution pour les cinq appels à la fonction puissance. Donc pour un appel à puissance(x,n), il y aura n+1 environnements dans la pile.
Mettre le résultat ici (code et figure).
Par défaut, Python limite le nombre d’appels récursifs dans une fonction à 1000.
Si vous dépassez les 1000, l'exception suivante s'affichera RecursionError: maximum recursion depth exceeded.
Cette limite, fixée à 1000 appels récursifs , peut être modifiable avec la fonction setrecursionlimit disponible dans le module sys.
Par exemple, pour passer cette limite à
2000 appels maximum, on exécutera le code Python suivant :
import sys
sys.setrecursionlimit(2000)
Remarque : La récursion dans d’autres langages. Certains langages de programmation, plus spécialisés que Python dans l’écriture de fonctions récursives, savent dans certains cas éviter de placer de trop nombreux environnements d'appel dans la pile. Cela leur permet dans les cas en question de s'affranchir de toute limite relative au nombre d'appels emboîtés. C’est
le cas notamment des langages fonctionnels (Lisp, Scala, ...).
Mettre le résultat ici (code et figure).
Donner une définition récursive qui correspond au calcul de la fonction factorielle n! définie par nl=1x2x...xn si n > 0 et 0! = 1, puis le code d’une fonction fact(n) qui implémente cette définition (fact(5)=120).
Mettre le résultat ici (code et figure).
( n = 1 si n = 0,
fact(n) = (
( n x fact(n-1) si n>0.
def fact(n):
if n == 0 :
return 1
else:
return n * fact(n - 1)
print(fact(5))
Soit u, la suite d’entiers définie par
Un+i = Un/2 si Un est pair,
- 3xUn+1 sinon.
avec U0 un entier quelconque plus grand que 1.
Écrire une fonction récursive syracuse(u_n) qui affiche les valeurs successives de la suite w, tant que w, est splus grand que 1
Exemple pour syracuse(20)
20
10
5
16
8
Mettre le résultat ici (code et figure).
def syracuse(u_n):
print (u_n)
if u_n > 1:
if u_n % 2 == 0:
syracuse(u_n // 2)
else:
syracuse (3 * u_n + 1)
syracuse(20)
On considère la suite u, définie par la relation de récurrence suivante, où a et b sont des réels quelconques :
( a€ℝ si n =0
Un = ( b€ℝ si n=1
( 3Un-1 + 2Un-2 + 5 si n≥2
Écrire une fonction récursive serie(n, a, b) qui renvoie le n-ème terme de cette suite pour des valeurs a et b données en paramètres.
Exemple : serie(20,1,5,5.3) = 211709824932.3
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def serie(n, a, b):
if n == 0 :
return a
elif n == 1 :
return b
else:
r = 3 * serie(n - 1, a, b) + 2 * serie(n - 2, a, b) +5
return r
print(serie(20,1.5,5.3))
Écrire une fonction récursive boucle(i ,k) qui affiche les entiers entre i et k.
Par exemple, boucle(0,3) doit afficher : 0 1 2 3.
Mettre le résultat ici (code et figure).
def boucle(i,k):
if i <= k:
print(i)
boucle(i+1, k)
boucle(0,3)
Écrire une fonction récursive pgcd(a, b) qui renvoie le PGCD de deux entiers a et b.
Exemple pgcd(96,36)=12
Mettre le résultat ici (code et figure).
def pgcd(a, b):
if a == 0:
return b
else :
return pgcd(b % a, a)
Écrire une fonction récursive nombre_de_chiffres(n) qui prend un entier positif ou nul n en argument et renvoie son nombre de chiffres.
Par exemple, nombre_de_chiffres(34126) doit renvoyer 5.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def nombre_de_chiffres(n):
if n <= 9:
return 1
else:
return 1 + nombre_de_chiffres(n // 10)
print(nombre_de_chiffres(34126))
En s'inspirant de l'exercice précédent, écrire une fonction récursive nombre _de_bits_1(n) qui prend un entier positif ou nul et renvoie le nombre de bits valant 1 dans la représentation binaire de n.
Par exemple : nombre _de_bits_1(1100100)=3
Mettre le résultat ici (code et figure).
Écrire une fonction récursive appartient(v, t, i) prenant en paramètres une valeur v, un tableau t et un entier i et renvoyant True si v apparaît dans t entre l’indice i (inclus) et len (t) (exclu), et False sinon.
On supposera que i est toujours compris entre 0 et len(t).
Exemple :
t = [1,3,5,6,7,9,10]
appartient(7,t,5) = False
appartient(7,t,3) = True
Mettre le résultat ici (code et figure).
def appartient(v, t, i):
if i == len(t):
return False
else:
return t[i] == v or appartient(v, t, i + 1)
t = [1,3,5,6,7,9,10]
print(appartient(7,t,5))
print(appartient(7,t,3))
Le triangle de Pascal (nommé ainsi en l’honneur au mathématicien Blaise Pascal) est une présentation des coefficients binomiaux sous la forme d’un triangle défini ainsi de manière récursive :
( 1 si p=0 ou n = p,
C{n,p) = (
( C(n - 1 , p - 1) + C(n - 1,p) sinon.
Écrire une fonction récursive C(n,p) qui renvoie la valeur de C{n,p).
Exemple : C510,5) = 252
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def C(n,p):
if p == 0 or n == p :
return 1
else:
return C(n - 1, p - 1) + C(n - 1, p)
print(C(10,5))