La récursivité
Définition
• Définition
• Une fonction est récursive si elle s’appelle elle-même.
• Problème
• Appels infinis
Définition
• Solution
• Le cas Trivial (Base Case)
• Une condition qui détermine si le problème est terminé
Exemple du factoriel
• la fonction factorielle se définit comme : n! = n *(n - 1)!
• Cette définition est infinie, en ce sens qu’elle ne s’achève pas. Pour
être calculable, il faut avoir une condition d’arrêt. 0! = 1 représente
notre condition d’arrêt.
• def fact(n:int)->int:
if(n==0):
return 1
else:
return n*fact(n-1)
• print(5,"!=",fact(5))
Exemple du factoriel
• la fonction factorielle se définit comme : n! = n *(n - 1)!
• Cette définition est infinie, en ce sens qu’elle ne s’achève pas. Pour être
calculable, il faut avoir une condition d’arrêt. 0! = 1 représente notre
condition d’arrêt.
• def fact(n:int)->int:
if(n==0):
return 1
else:
return n*fact(n-1)
• print(5,"!=",fact(5))
• 5 != 120
terminaison d’une fonction récursive
• Pour s’assurer de la terminaison d’une fonction récursive, on doit respecter les
règles suivantes :
• • La fonction doit contenir un ou plusieurs cas de base ne comportant pas d’appel
récursif.
• Dans la fonction fact : c’est le cas n = 0.
• • Les appels de la fonction se font des arguments plus simple pour conduire aux
cas de base.
• Dans l’appel de fact(n) : les arguments successifs sont n − 1 > n − 2 > · · · > 0.
formulation récursive d’une fonction
• Toute formulation récursive d’une fonction possède au moins un cas
de base et un cas récursif. Une grande variété de formes est possible.
• Cas de base multiples (voir exemple suivant)
• Cas récursifs multiples (à fair en TD)
• Double récursion
• plusieurs appels à la fonction (voir exemple suivant)
Exemple: la fonction fibonacci
La fonction fibonacci(n) est définie récursivement, pour tout entier
naturel n, de la manière suivante :
Exemple: la fonction fibonacci
• def fibonacci(n):
if (n==0):
return 0
elif (n==1):
return 1
else :
return fibonacci(n-1)+fibonacci(n-2)
• print("fibonacci(",6,")=", fibonacci(6))
Exemple: la fonction fibonacci
• def fibonacci(n):
if (n==0):
return 0
elif (n==1):
return 1
else :
return fibonacci(n-1)+fibonacci(n-2)
• print("fibonacci(",6,")=",fibonacci(6))
• fibonacci( 6 )= 8
Construction d’un Algorithme récursif
• Pour trouver une solution récursive à un problème (si elle existe), on
doit:
• 1. Chercher à décomposer le problème en plusieurs sous-problèmes
du même type mais de tailles inférieures,
• 2. Déterminer l’action qui représente le cas trivial, et donner sa
solution.
• 3. Et en supposant connaitre l’action pour le cas d’ordre n-1, peut-on
prévoir le cas suivant, c’est-à-dire d’ordre (n).
• Si ces trois (03) conditions sont satisfaites, alors on peut envisager
l’emploie d’une méthode récursive.
exercices
• Exercice 1
• une fonction récursive pour calculer la somme d'une séquence:
1, 2,3, …, n
exercices
• Exercice 2
• écrire une fonction récursive qui calcule xn
exercices
• Exercice 3
• Ecrire une fonction récursive qui calcule le pgcd de deux entiers a et b
sachant que pgcd(a, b)= pgcd(b, r) où r est le reste dans la division
euclidienne de a par b.
exercices
• Exercice 4
• Ecrire une fonction récursive qui calcule la longueur d’une chaine de
caractères
exercices
• Exercice 5
• Ecrire une fonction récursive qui calcule la somme des éléments
d’une liste L.
exercices
• Exercice 6
• Soit la suite définie par :
• 𝑈𝑛= 1 si 𝑛≤2
• 3𝑈𝑛−1+𝑈𝑛−2 𝑠𝑖𝑛𝑜𝑛
• Ecrire une fonction récursive qui calcule le nième terme de la suite;
exercices
• Exercice 7
• Un tableau X est trié par ordre croissant si 𝑥(𝑖)≤𝑥(𝑖+1),∀𝑖, écrire une
fonction récursive permettant de vérifier qu’un tableau X est trié ou
non
