Algorithmique: la récursivité

I) Généralités
    1) Définition
    2) Exemple typique : la factorielle
    3) Limitation du nombre d’appels récursifs
    4) Conception et schéma simplifié d’une fonction récursive
II) Autres exemples
    1) Suites définies par une relation de récurrence simple
    2) Suite de Fibonacci
    3) La fonction puissance
    4) La fonction pgcd
    5) Ecrire un entier comme une somme de 1, 2, 3
    6) Recherche dichotomique d’un élément dans une liste triée
    7) p-listes strictement croissantes de{1, 2, ...,n}
    8) Tours de hanoi
III) Fonction itérative ou fonction récursive ?
    1) Le pour et le contre
    2) Etude d’un premier cas: la complexité d’une suite récurrente
    3) Etude d’un second cas: la complexité de la suite de Fibonacci
    4) Bilan: avantages et inconvénients de la récursivité

I) Généralités

1) Définition

Une fonction récursive est une fonction qui s’appelle elle-même lors de son exécution.
Une ligne de code où la fonction s’appelle elle-même est un appel récursif.

2) Exemple typique : la factorielle

  On sait que 0!=1 et que pour tout n 1 , n != n ( n - 1 ) ! . Cette remarque nous permet d’écrire de façon naturelle une version récursive de la fonction factorielle, calculant n ! pour un entier n quelconque:

def facto(n):
    if n == 0:                        # Cas de base
        return 1
    return n * facto(n-1)        # Appel récursif

Que se passe-t-il lors du calcul de facto(4) ?

|-- facto(4)
|  |-- facto(3)
|  |  |-- facto(2)
|  |  |  |-- facto(1)
|  |  |  |  |-- facto(0)
|  |  |  |  |  |-- return 1
|  |  |  |  |-- return 1
|  |  |  |-- return 2
|  |  |-- return 6
|  |-- return 24
24

Il y a deux phases lors de ce calcul:
    (1) La phase de “descente” qui produit les appels succesifs de la fonction facto() jusqu’à ce que l’on arrive au cas de base (n = 0)
    (2) La phase de “remontée” qui retourne les valeurs des appels successifs précédents, jusqu’à l’appel initial et donc le résultat

Remarquons que le calcul de facto(-1), par exemple, entraîne une infinité d’appels de la fonction facto(), et donc pas de réponse...

3) Limitation du nombre d’appels récursifs

  Certains langages imposent une limitation du nombres d’appels récursifs . Pour Python, cette limitation est par défaut à N = 1000, mais peut être modifiée:

import sys                                # on import le module sys
sys.setrecursionlimit(100000)        # Par exemple

4) Conception et schéma simplifié d’une fonction récursive

  Une fonction f ( P ) avec P une liste de paramètres peut avoir une écriture récursive lorsque l’évaluation de f ( P ) peut se ramener à l’évaluation de f ( P ' ) avec P ' plus petit que P : après un nombre fini de répétitions de cette procédure, on doit se ramener à l’évaluation de f ( P 0 ) dont le résultat est connu.
  Le  schéma simplifié d’une fonction   f ( P ) récursive est donc:

def f(P):
    if P = P0                # cas de base:
        return ...            # résultat connu
    return ...f(P’)...    # autres cas: appel récursif

II) Autres exemples

  Dans ces exemples on montre le déroulement des phases de descente et de remontée lors de l’exécution.

1) Suites définies par une relation de récurrence simple

Toutes les suites ( u n ) définies par leur premier terme u 0 et une relation du type: n N , u n + 1 = f ( u n ) peuvent se calculer naturellement de manière récursive:

def u(n):
    if n == 0:
        return = u0
    return f(u(n-1))

2) Suite de Fibonacci

  On peut faire plusieurs appels récursifs lors de la définition de la fonction. Par exemple, une suite définie par une relation de récurrence d’ordre ≥ 2 peut aussi s’écrire naturellement de manière récursive. Pour la suite de Fibonacci:

def fibo(n):
    if n < 2:
        return 1
    return fibo(n-1) + fibo(n-2)

  Voilà le déroulement des appels récursifs puis des retours pour fibo(6). Dessiner l’arbre des appels pour comprendre dans quel ordre ils sont effectués.

|-- fibo(5)
|  |-- fibo(4)
|  |  |-- fibo(3)
|  |  |  |-- fibo(2)
|  |  |  |  |-- fibo(1)
|  |  |  |  |  |-- return 1
|  |  |  |  |-- fibo(0)
|  |  |  |  |  |-- return 1
|  |  |  |  |-- return 2
|  |  |  |-- fibo(1)
|  |  |  |  |-- return 1
|  |  |  |-- return 3
|  |  |-- fibo(2)
|  |  |  |-- fibo(1)
|  |  |  |  |-- return 1
|  |  |  |-- fibo(0)
|  |  |  |  |-- return 1
|  |  |  |-- return 2
|  |  |-- return 5
|  |-- fibo(3)
|  |  |-- fibo(2)
|  |  |  |-- fibo(1)
|  |  |  |  |-- return 1
|  |  |  |-- fibo(0)
|  |  |  |  |-- return 1
|  |  |  |-- return 2
|  |  |-- fibo(1)
|  |  |  |-- return 1
|  |  |-- return 3
|  |-- return 8
8

3) La fonction puissance

Comme x n = x * x n - 1 , on peut calculer pour x R et n N     f ( x , n ) = x n de manière récursive:

def puissance_naive(x, n):
    if n == 0:
        return 1
    return x * puissance(x, n - 1)

  L’algorithme d’exponentiation rapide exploite l’idée suivante: le calcul de a 2 n ou de a 2 n + 1 se ramène à celui de a n en remarquant que: { a 2 n + 1 = a * ( a n ) 2 a 2 n = ( a n ) 2 pour a , n N . Cela se traduit naturellement par une version récursive:

def puissance_rapide(x, n):
    """exponentiation rapide (calcul de x^n). Version récursive"""
    if  n == 0:
        return 1
    a = puissance_rapide(x, n // 2)
    if n % 2 == 0:
        return a * a
    return x * a * a

  Voilà un exemple d’exécution:

|-- puissance_rapide(3, 11)
|  |-- puissance_rapide(3, 5)
|  |  |-- puissance_rapide(3, 2)
|  |  |  |-- puissance_rapide(3, 1)
|  |  |  |  |-- puissance_rapide(3, 0)
|  |  |  |  |  |-- return 1
|  |  |  |  |-- return 3
|  |  |  |-- return 9
|  |  |-- return 243
|  |-- return 177147
177147

4) La fonction pgcd

Si r est le reste de la division de a par b, alors pgcd(a, b) = pgcd(b, r). On peut alors écrire une fonction pgcd(a, b) récursive:

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)

  Par exemple:

|-- pgcd(1234567, 7654321)
|  |-- pgcd(7654321, 1234567)
|  |  |-- pgcd(1234567, 246919)
|  |  |  |-- pgcd(246919, 246891)
|  |  |  |  |-- pgcd(246891, 28)
|  |  |  |  |  |-- pgcd(28, 15)
|  |  |  |  |  |  |-- pgcd(15, 13)
|  |  |  |  |  |  |  |-- pgcd(13, 2)
|  |  |  |  |  |  |  |  |-- pgcd(2, 1)
|  |  |  |  |  |  |  |  |  |-- pgcd(1, 0)
|  |  |  |  |  |  |  |  |  |  |-- return 1
|  |  |  |  |  |  |  |  |  |-- return 1
|  |  |  |  |  |  |  |  |-- return 1
|  |  |  |  |  |  |  |-- return 1
|  |  |  |  |  |  |-- return 1
|  |  |  |  |  |-- return 1
|  |  |  |  |-- return 1
|  |  |  |-- return 1
|  |  |-- return 1
|  |-- return 1
1

  Cette fonction pgcd() est un exemple de fonction récursive terminale: une fonction à récursivité terminale (dite tail-recursive en anglais) est une fonction où l’appel récursif est la dernière instruction à être évaluée. Il n’y a pas de calcul autre que l’appel récursif dans l’instruction return.

5) Ecrire un entier de toutes les façons possibles comme une somme de 1, 2, 3

  Le calcul de toutes les écritures E ( n ) d’un entier n comme une somme de 1, 2, 3 se ramène à E ( n - 1 ) (en ajoutant 1), E ( n - 2 ) (en ajoutant 2) et E ( n - 3 ) (en ajoutant 3).

def ajout(liste_mots, caract):
    """ fonction auxilliaire"""
    return [ "{0}{1}".format(caract, mot) for mot in liste_mots ]

def un_deux_trois(n):
    """ Ecriture de n comme une somme de 1, 2, 3"""
    if n == 1:
        return ["1"]
    if n == 2:
        return ["11", "2"]
    if n == 3:
        return ["111", "12", "21", "3"]
    return ajout(un_deux_trois(n - 1), "1") + ajout(un_deux_trois(n - 2), "2")\
              + ajout(un_deux_trois(n - 3), "3")

  Par exemple:

|-- un_deux_trois(5)
|  |-- un_deux_trois(4)
|  |  |-- un_deux_trois(3)
|  |  |  |-- return ['111', '12', '21', '3']
|  |  |-- un_deux_trois(2)
|  |  |  |-- return ['11', '2']
|  |  |-- un_deux_trois(1)
|  |  |  |-- return ['1']
|  |  |-- return ['1111', '112', '121', '13', '211', '22', '31']
|  |-- un_deux_trois(3)
|  |  |-- return ['111', '12', '21', '3']
|  |-- un_deux_trois(2)
|  |  |-- return ['11', '2']
|  |-- return ['11111', '1112', '1121', '113', '1211', '122', '131', '2111', '212', '221', '23', '311', '32']
['11111', '1112', '1121', '113', '1211', '122', '131', '2111', '212', '221', '23', '311', '32']

6) Recherche dichotomique d’un  élément dans une liste triée

  La recherche d’un élément elem dans une partie tab[deb: fin] d’un tableau tab trié par ordre croissant se ramène à la recherche de elem dans la partie tab[deb: milieu] ou tab[milieu: fin] en comparant tab[milieu] à elem, pour savoir si elem est dans la partie gauche ou droite de tab[deb: fin].

def rech_dicho(tab, elem):
    """ Position de elem dans la liste triée tab (-1 si elem n'y est pas)"""
    def moteur(deb, fin):
        """ moteur de recherche dichotomique récursif"""
        if deb > fin:
            return -1
        milieu = (deb + fin) // 2
        m = tab[milieu]
        if elem < m:
            return moteur(deb,milieu - 1)
        if elem > m:
            return moteur(milieu + 1, fin)
        return milieu
    return moteur(0, len(tab) - 1

  L’intérêt d’écrire une sous fonction pour la recherche récursive est d’éviter de passer la liste tab dans les paramètres des appels récursifs en plus de deb et fin. La fonction principale rec_dicho() enveloppe le moteur de recherche récursif.
  Par exemple:

t = [1,3,5,6,6,8,9,14,15]
print(rech_dicho(t, 7))
print(rech_dicho(t, 14))

|-- moteur(0, 8)
|  |-- moteur(5, 8)
|  |  |-- moteur(5, 5)
|  |  |  |-- moteur(5, 4)
|  |  |  |  |-- return -1
|  |  |  |-- return -1
|  |  |-- return -1
|  |-- return -1
-1
|-- moteur(0, 8)
|  |-- moteur(5, 8)
|  |  |-- moteur(7, 8)
|  |  |  |-- return 7
|  |  |-- return 7
|  |-- return 7
7

7) p-listes strictement croissantes de {1, 2,..., n}

  On peut calculer de manière itérative l’ensemble des p-listes strictement croissantes de { 1 , 2 , ... , n } :

def listes_strictement_croissantes_I(p,n):
    """ Liste des p-listes strictement croissantes de {1,2,...,n}. Itérative"""
    pos, res, s = p - 1, [], list(range(1, p + 1))
    while pos >= 0 and s[pos] < n:
        res.append(list(s))
# Calcul de la liste s suivante
        s[pos] += 1
        for i in range(1, p - pos):
            s[pos + i] = s[pos] + i
        pos = p-1
# Recherche du point de décrochage pour le calcul quivant
        while (pos >= 0) and (s[pos] == n + 1 + pos - p):
            pos -= 1
    res.append(list(s))
    return res
    
print(listes_strictement_croissantes_I(3, 5))
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

  Mais c’est plus naturel de faire ce calcul de manière récursive.
  Si l’on sait calculer la liste L ( deb , k - 1 ) des ( k - 1 ) - listes strictement croissantes de { deb , ... , n } , alors on obtiendra les k - listes strictement croissantes de { deb , ... , n } en choisissant un entier i { deb , ... , n } et en lui ajoutant une ( k - 1 ) - liste strictement croissante de { i + 1 , ... , n } . Comme il faudra pouvoir ajouter à i une suite strictement croissante de k - 1 entiers plus petits que n ., alors il faudra que i i max avec i max + k - 1 = n , c’està dire i max = n - k + 1 .
  On enveloppe le moteur récursif dans la fonction principale, et il ne reste plus qu’à gérer les listes calculées; il y  a deux options:
      •   On peut passer en paramètre dans le moteur récursif la liste choix en cours de calcul
      •• On peut utiliser une liste choix unique extérieure au moteur de calcul.
  La seconde option est le plus économique en terme de mémoire utilisée.

def listes_strictement_croissantes_R(p,n):
    """ Liste des p-listes strictement croissantes de {1,2,...,n}. Récursive
    Première option"""
    res = []
    def moteur_Lsc(deb, choix, k):
        if k == 0:
            res.append(choix)
        else:
            for i in range(deb, n + 2 - k):
                moteur_Lsc(i + 1, choix + [i], k - 1)
    moteur_Lsc(1, [], p)
    return res
    
print(listes_strictement_croissantes_R(3, 5))
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

def listes_strictement_croissantes_R(p,n):
    """ Liste des p-listes strictement croissantes de {1,2,...,n}. Récursive.
    Seconde option"""
    def moteur_Lsc(deb, k):
        if k == 0:
            res.append(list(choix))
        else:
            for i in range(deb, n + 2 - k):
                choix[p - k] = i
                moteur_Lsc(i + 1, k - 1)
    res, choix = [], [0] * p
    moteur_Lsc(1, p)
    return res

8) Tours de Hanoi

Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents et empilés par diamètres décroissants sur un piquet de « départ » vers un piquet d’« arrivée » en passant par un piquet « intermédiaire » avec les règles suivantes :
    (1) on ne peut déplacer qu’un seul disque à la fois.
    (2) on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

  Pour trois disques, voilà une solution: cours_algo_recursivite_1.gif

  On modélise une solution par la liste des déplacements d’un piquet à l’autre, les piquets étant numérotés 1, 2 et 3. Un dépacement du piquet a vers le piquet b est le couple ( a , b ) . La solution ci-dessus pour  est modélisée par la liste D = [ ( 1 , 3 ) , ( 1 , 2 ) , ( 3 , 2 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 3 ) , ( 1 , 3 ) ] .  On veut écrire une fonction hanoi ( n ) (avec n N * ) calculant une solution pour le déplacement d’une pile de n disques du piquet 1 vers le piquet 3.
  Pour pouvoir bouger ces disques sur le troisième piquet il va nécessairement falloir bouger le disque le plus grand depuis sa position actuelle vers le troisième piquet. Cela signifie qu'à ce moment là tous les autres disques doivent être sur le piquet du milieu. Il faut donc trouver une suite de déplacements pour les y emmener...et on retrouve un problème similaire à celui de départ ! C'est le signe qu'il va falloir utiliser un algorithme récursif. Il aura donc la forme générale suivante :

Hanoi(<liste d'arguments>)
  // Cas de base
  // Cas général

  Tout d'abord, regardons le cas de base de l'algorithme, c'est-à-dire le cas le plus simple à gérer, quand il n'y a aucun disque ! Il ne faut alors rien faire du tout. L'algorithme devant savoir combien de disques il faut déplacer, on va lui donner en argument.

Hanoi(nbDisques, <liste d'arguments>)
   // Cas de base
   Si nbDisques = 0
      Quitter la fonction
   // Cas général

  Regardons maintenant le cas général (au moins un disque). Nous avons vu qu'il pouvait se traiter en trois étapes :
    (1) On déplace tous les disques sans le dernier vers le piquet du milieu.
    (2) On déplace le dernier disque (le plus gros) vers le piquet de droite.
    (3) On déplace tous les autres disques depuis le piquet du milieu vers celui de droite.
  Pour faire cette seconde étape nous allons appliquer la même idée mais les piquets de gauche/milieu/droite n’ont plus le même rôle (le piquet de départ est désormais celui du milieu). On va donc passer en argument à notre algorithme les numéros des piquets.    

Hanoi(nbDisques, Départ, Intermédiaire, Arrivée)
   Si nbDisques = 0
      Quitter la fonction
   HanoiDisques(nbDisques - 1, Départ, Arrivée, Intermédiaire)
   Enregistrer le déplacement (Départ -> Arrivée)
   Hanoi(nbDisques - 1, Intermédiaire, Départ, Arrivée)

  On enveloppe le moteur récursif de calcul dans la fonction principale:

def hanoi(n):
    """ Déplacement solution de T1 vers T3 pour les tours de Hanoi"""
    sol = []
    def moteur(k, a, b, c):
        if k == 0:
            return
        else:
            moteur(k - 1, a, c, b)
            sol.append((a,c))
            moteur(k - 1, b, a, c)
    moteur(n, 1, 2, 3)
    return sol

print(hanoi(4))
[(1, 2), (1, 3), (2, 3), (1, 2), (3, 1), (3, 2), (1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (2, 3), (1, 2), (1, 3), (2, 3)]

III) Fonction itérative ou fonction récursive ?

1) Le pour et le contre

  Dans les exemples proposés dans le II) on peut souvent écrire une version itérative (boucle “pour” ou “tant que”) de la fonction. Quelle  est la meilleure version ? Voici quelques éléments de réponse:

Pour une version récursive d’une fonction:
     (1) C’est une manière naturelle d’écrire de nombreuses fonctions.
    (2) C’est parfois la seule manière simple d’écrire certaines fonctions.
    (3) Il  est souvent facile de démontrer la terminaison et la correction d’une fonction récursive.

Contre une version récursive d’une fonction:
    (1) La consommation de mémoire (complexité spatiale) est plus importante que pour une version itérative. On ne s’occupe guère de ce facteur de limitation, difficile à évaluer,  dans ce cours.
    (2) La complexité (temporelle) d’un algorithme récursif peut être rédhibitoire, surtout s’il est mal conçu: les deux exemples suivants illustrent ce point.

2) Etude d’un premier cas: la complexité d’une suite récurrente

  Etudions la complexité des trois versions suivantes du calcul de la suite ( u n ) définie par:
u 0 = 2 et pour tout entier n , u n + 1 = 1 2 ( u n + 1 u n ) .

Notons C ( n ) le nombre d'opérations arithmétiques élémentaires nécessaires au calcul de u n . (on néglige les affectations et les comparaisons)

On étudie une version itérative et deux versions récursives.

def u1(n):
    u = 2
    for i in range(n):
        u = 0.5 * (u + 1 / u)
    return u

On fait trois opérations dans chaque itération donc C 1 ( n ) = 3 n . La complexité est linéaire (très bonne).

def u2(n):
    if n == 0:
        return 2
    return 0.5 * (u2(n - 1) + 1 / u2(n - 1))

On a C 2 ( 0 ) = 0 et  pour n N * ,   C 2 ( n ) = 2 C 2 ( n - 1 ) + 3 . On en déduit (récurrence facile) que C 2 ( n ) = 3 ( 2 n - 1 ) . La complexité est géométrique (rédhibitoire).

def u3(n):
    if n == 0:
        return 2
    x = u3(n-1)
    return 0.5 * (x + 1 / x)

On a C 3 ( 0 ) = 0 et  et  pour   n N * , C 3 ( n ) = C 3 ( n - 1 ) + 3 . On en déduit que C 3 ( n ) = 3 n . La complexité est linéaire (très bonne).

Bilan:
    - Les versions u1(n) et u3(n) ont la même complexité. La version u3(n) consomme plus de mémoire que u1(n), mais cela reste négligeable.
    - La version u2(n), la plus naturelle, est à proscrire absolument.

3) Etude d’un second cas: la complexité de la suite de Fibonacci

  Etudions la complexité des trois versions suivantes du calcul de la suite de Fibonacci. Notons C ( n ) le nombre d’opérations arithmétiques élémentaires nécessaires au calcul de F n .
On étudie une version itérative et deux versions récursives.

def fibo1(n):
    a, b = 1, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b

On fait une addition par itération, donc C 1 ( n ) = n - 1 .  La complexité est linéaire (très bonne). Mais:

def fibo2(n):
    if n < 2:
        return 1
    return fibo2(n-1) + fibo2(n-2)

  On a C 2 ( 0 ) = C 2 ( 1 ) = 0 et  pour n ≥ 2,   C 2 ( n ) = C 2 ( n - 1 ) + C 2 ( n - 2 ) + 1 . On en déduit (calcul classique) que C 2 ( n ) = 1 5 ( ϕ n + 1 + 1 ϕ n + 1 ) - 1 (avec ϕ = 1 + 5 2 1.6 . La complexité est géométrique (rédhibitoire). On propose alors la version suivante, la fonction fibo3(n) enveloppe le moteur de calcul récursif:

def fibo3(n):
    def moteur(k, a,b):
        if k == 0:
            return a
        return moteur(k - 1, b, a + b)
    return moteur(n, 1, 1)

On fait une addition par appel récursif donc C 3 ( n ) = n .  La complexité est linéaire (très bonne). La fonction moteur() est récursive terminale.

print(fibo3(6))

|-- moteur(6, 1, 1)
|  |-- moteur(5, 1, 2)
|  |  |-- moteur(4, 2, 3)
|  |  |  |-- moteur(3, 3, 5)
|  |  |  |  |-- moteur(2, 5, 8)
|  |  |  |  |  |-- moteur(1, 8, 13)
|  |  |  |  |  |  |-- moteur(0, 13, 21)
|  |  |  |  |  |  |  |-- return 13
|  |  |  |  |  |  |-- return 13
|  |  |  |  |  |-- return 13
|  |  |  |  |-- return 13
|  |  |  |-- return 13
|  |  |-- return 13
|  |-- return 13
13

Finalement:
    - La version fibo2(n), la plus naturelle, est à proscrire absolument.
    - Les versions fibo1(n) et fibo3(n) ont la même complexité.
    - Pour écrire une version récursive efficace fibo3(n), il faut travailler avec deux termes consécutifs de la suite.

4) Bilan: avantages et inconvénients de la récursivité

- La récursivité est une technique de programmation naturelle, élégante, sobre, efficace, utile, parfois indispensable.
-  Il faut réfléchir avec soin à la conception de l’algorithme pour ne pas avoir une complexité “mortelle”.

IV) Compléments

1) Structure d’une fonction récursive terminale, décursification

  Une fonction à récursivité terminale est une fonction où l’appel récursif est la dernière instruction à être évaluée. Il n’y a pas de calcul après l’appel récursif. On peut la schématiser par:

def f_Rec(P):
    Si cas de base:
        Traitement de terminaison
    Sinon
        Instructions_1             # instructions éventuelles et sans appel récursif
        (return) f_Rec(g(P))        # Appel récursif sur g(P) plus petit que P

  Il est facile de la dérécursifier, c’est à dire d’en écrire une version itérative équivalente:

def f_Iter(P):
    Tant que non Cas de base:
        Instructions_1
        P = g(P)    
    Traitement de terminaison

Par exemple:

def pgcd_Rec(a, b):
    if b == 0:
        return a
    return pgcdRec(b, a % b)

def pgcd_Iter(a, b):
    while b > 0:
        a, b = b, a % b
    return a

Et:

def fibo_Rec(n):
    def moteur(k, a,b):
        if k == 0:
            return a
        return moteur(k - 1, b, a + b)
    return moteur(n, 1, 1)

def fibo_Iter(n):
    a, b, k = 1, 1, n
    while k > 0:
        a, b, k = b, a + b, k - 1
    return a

2) Structure d’une fonction récursive non terminale, décursification

  Une fonction à récursivité non terminale est une fonction où l’appel récursif n’est la dernière instruction à être évaluée.

def f_Rec(P):
    Si cas de base:
        Traitement de terminaison
    Sinon
        Instructions_1             # instructions éventuelles et sans appel récursif
        (return) f_Rec(g(P))        # Appel récursif sur g(P) plus petit que P
        Instructions_2                # instructions sans appel récursif

  Il est plus difficile de la dérécursifier. Il faut utiliser une pile LIFO (Last In, First Out) pour empiler/dépiler les paramètres des appels récursif. la situation se complique lorsqu’il aut en plus gérer les variables locales éventuelles. La version itérative ( sans les variables locales)est la suivante:

def f_Iter(P):
    Pile = []            # Initialisation de la pile d’appels
    Tant que non Cas de base:
        Instructions_1
        Empiler(P)
        P = g(P)
    Traitement de terminaison
    Tant que la pile n’est pas vide:
        Dépiler(Q)
        Instructions_2

Par exemple, pour la factorielle:

def facto_Rec(n):
    if n == 0:
        return 1
    return n * facto(n-1)

def facto_Iter(n):
    pile = []
    while n > 0:
        pile.append(n)
        n = n  - 1
    res = 1
    while pile != []:
        m = pile.pop()
        res = res * m
    return res

© 2015 - Eric Obermeyer      Powered by