Diaporama n°6¶

Récursivité¶

Fonction récursive :¶

Une fonction qui s'appelle elle-même ...

In [ ]:
def ma_premiere_fonction_recursive(n):
    ...
    ma_premiere_fonction_recursive(...)
    ....

NB : z = f(f(3)) n'est pas de la récursité. Il y a deux appels successifs à f¶

Exemple 1 : sommer les entiers de 0 à n¶

Version itérative¶

In [4]:
def sommeIt(n):
    s = 0
    for i in range(n+1):
        s += i
    return s

sommeIt(5)
Out[4]:
15

Version optimisée "mathématiquement"¶

In [6]:
def sommeFormule(n):
    return n*(n+1)//2

sommeFormule(5)
Out[6]:
15

Version récursive¶

On pose $S_n = \sum_{i=0}^n i$

$S_0 = 0$, et pour $n>0$, $S_n = S_{n-1} + n$ ...

In [2]:
def sommeR(n):
    if n==0:
        return 0
    else:
        s = sommeR(n-1)
        return s+n

sommeR(5)
Out[2]:
15

magique ???

Avec Python Tutor

Appels imbriqués¶

Les appels imbriqués se font dans un ordre précis, celui dicté par le programme

Pour répondre au problème $n$, on s'aide de la réponse au problème $n-1$, qui s'aide de la réponse au problème $n-2$ ... ainsi de suite ...

et la réponse au problème 0 est triviale

Attention aux analogies mathématiques¶

On pose $S_n = \sum_{i=0}^n i$. Certes $S_n = n + S_{n-1}$ ...

Mais ce n'est pas ce genre d'égalité à elle seule qui justifie que tout se passe bien ...

In [8]:
def sommeR(n):
    s = sommeR(n+1)
    return s - (n+1)

Avec Pyton Tutor

un appel à cette fonction ne termine pas

Attention : limitation du nombre d'appels imbriqués¶

In [4]:
sommeR(3000)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-4-a1a601c64b2a> in <module>
----> 1 sommeR(3000)

<ipython-input-2-f912480cd332> in sommeR(n)
      3         return 0
      4     else:
----> 5         s = sommeR(n-1)
      6         return s+n
      7 

... last 1 frames repeated, from the frame below ...

<ipython-input-2-f912480cd332> in sommeR(n)
      3         return 0
      4     else:
----> 5         s = sommeR(n-1)
      6         return s+n
      7 

RecursionError: maximum recursion depth exceeded in comparison

Exemple 2 : le nième terme de la suite de Fibonacci¶

Suite mathématique célèbre : 0 ; 1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ... (une histoire de reproduction de lapins ...) définie par :

$u_0 = 0$, $u_1 = 1$ et $\forall n \in \mathbb{N}\setminus\{0;1\}$, $u_{n}=u_{n-1}+u_{n-2}$

Et comme par magie, on peut définir ...

In [10]:
def fibo(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        a = fibo(n-2)
        b = fibo(n-1)
        return a+b
        
fibo(6)
Out[10]:
8

avec Python Tutor

Il y a de trop nombreux appels, souvent identiques ... (c'est beaucoup moins magique ...)

Attention : appels répétés¶

In [12]:
import time

t1 = time.time()
z = fibo(33) # version récursive
t2 = time.time()

print(z)
print(t2-t1) # durée d'éxecution
3524578
2.993722677230835

NB : 3 secondes de calcul pour obtenir le 33ième terme de la suite (c'est beaucoup trop long !)

Mémoïsation¶

Principe : on conserve les résultats des appels déjà réalisés (cf TP Récursivité)

In [1]:
def fibo_memo(memo, n):
    if memo[n] != -1:
        return memo[n]
    else :
        v = fibo_memo(memo,n-2) + fibo_memo(memo,n-1)
        memo[n] = v
        return v
    
def fibo2(n):
    memo = [-1]*(n+1)
    memo[0] = 0
    memo[1] = 1
    return fibo_memo(memo,n)
In [2]:
import time

t1 = time.time()
z = fibo2(33) # version mémoïsée
t2 = time.time()

print(z)
print(t2-t1)  # durée d'éxecution
3524578
0.00041675567626953125

NB : quelques micro-secondes de calcul pour obtenir le 33ième terme de la suite

Concevoir un algorithme récursif¶

Le jeu des tours de Hanoï¶

image.png

Jeu en ligne