# TD5 : Récursivité

## Définitions

Une fonction **récursive** est une fonction qui s'appelle elle-même. Elle doit avoir une manière de gérer une **itération** ainsi qu'une **condition d'arrêt**.

Le gros problème d'une fonction récusive sont les ressources nécessaires et l'explosion de la taille de la pile d'appel. Par exemple, la fonction `recsum`:

def recsum(x):
    if (x === 0):
        return 0
    else: 
        return x + recsum(x - 1)

Nécessite la pile d'appel suivante pour un appel à `recsum(5)`:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

Le principal problème vient de la ligne 4 et de l'impossibilité pour l'interprète du langage de compléter le calcul sans le résultat...

Une fonction **récursive terminale** corrige le problème en rendant l'appel à la fonction récursive pur et sans autre opération. Par exemple, la fonction `tailrecsum` :

def tailrecsum(x, running_total):
    if (x == 0):
        return running_total
    else:
        return tailrecsum(x - 1, running_total + x)

Dans ce cas, la pile d'appel pour `tailrecsum(5)` devient :

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

## Exercices

1. **Factorielle**
Calcul de `n! = 1 * 2 * 3 * ... * n`

**Solution :**

def factorielle(n):
    if n <= 1:
        return 1
    return n * factorielle(n-1)

---

2. **Fibonacci**
Calcul de `u0 = 0, u1 = 1 et un+2 = un+1 + un`

**Solution :**

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else: 
        return fibonacci(n-1) + fibonacci(n-2)

---

3. **Fibonacci terminale**
**Solution :**

def fibonacci_term(a, b, n):
    if n > 1:
        return fibonacci_term(b, a+b, n-1)
    elif n == 1:
        return b
    else:
        return a

---

4. **Fonction d'Ackermann**

ack(0,n) = n+1
ack(m,0) = ack(m-1,1)
ack(m,n) = ack(m-1, ack(m, n-1))

**Solution :**

def ack(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ack(m - 1, 1)
    return ack(m - 1, ack(m, n - 1))

---

5. **PGCD**

**Solution :**

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

---

6. **Flocon de Koch**

Code donné :

import koch_drawer as kd

def decoupe(pd, pf, n):
    # COMMENT UTILISER N?


    # Trace le segment
    kd.draw(pd, pf)

    # Calcule les points p1/3, ps et p2/3 du schéma
    # Utiliser ces points pour les appels récursifs quand il le faut
    p1 = ((2*pd[0]+pf[0])/3, (2*pd[1]+pf[1])/3)
    p2 = ((pd[0]+2*pf[0])/3, (pd[1]+2*pf[1])/3)
    ps = ((pd[0]+pf[0])/2 - (pf[1]-pd[1])/(2*(3**0.5)), \
          (pd[1]+pf[1])/2 + (pf[0]-pd[0])/(2*(3**0.5)))


# pour traiter le flocon :
# ecrire une fonction koch(flocon, n)
# qui découpe (n fois) chaque segment de la liste flocon
def koch(flocon, n):
    ...

if __name__=="__main__":
    x = (0,0)
    y = (1,0)
    z = (0.5, 3**0.5/2)
    courbe = [x, y]
    flocon = [x, z, y, x]
    
    n = 7

    # Pour découper 
    decoupe(x, y, n)
    koch(flocon, n)
    
    print(kd.longueur())
    
    kd.draw_koch()

**Solution :**

def decoupe(pd, pf, n):
    if n==0:
        # Trace le segment : récursion maximale atteinte
        kd.draw(pd, pf)
    else:
        # Calcule les points p1/3, ps et p2/3 du schéma
        p1 = ((2*pd[0]+pf[0])/3, (2*pd[1]+pf[1])/3)
        p2 = ((pd[0]+2*pf[0])/3, (pd[1]+2*pf[1])/3)
        ps = ((pd[0]+pf[0])/2 - (pf[1]-pd[1])/(2*(3**0.5)), \
              (pd[1]+pf[1])/2 + (pf[0]-pd[0])/(2*(3**0.5)))
        decoupe(pd, p1, n-1)
        decoupe(p1, ps, n-1)
        decoupe(ps, p2, n-1)
        decoupe(p2, pf, n-1)

def koch(courbe, n):
    for i in range(len(courbe)-1):
        decoupe(courbe[i], courbe[i+1], n)

###### tags: `python`