# Cours 3 : Récursivité

## Rappel : la pile d'exécution

Au cours de l'exécution d'un programme les variables sont stockées dans la mémoire sous forme d'une **pile**. A chaque appel de fonction, un espace mémoire est réservé pour les variables de la fonction.

**Exemple** 


```python
def fonction1(a):
    c = a + 1
    return c

def fonction2(b):
    return fonction1(b+1)

a = fonction2(3)
a
```




    5



Voici une image simplifiée de l'évolution de la pile lors de l'exécution



On va utiliser le petit bout de code suivant pour suivre en direct les appels de fonctions, exécutez la cellule qui définit la fonction `printAppelsFonctions` puis regardons comment on l'applique sur notre petit bout de code.


```python
import functools

def printAppelsFonctions(func):
    """Print the function signature and return value"""
    @functools.wraps(func)
    def wrapper_debug(*args, **kwargs):
        args_repr = [repr(a) for a in args]                      
        kwargs_repr = [f"{k}={v!r}" for k, v in kwargs.items()]  
        signature = ", ".join(args_repr + kwargs_repr)           
        print(f"Appel de {func.__name__}({signature})")
        value = func(*args, **kwargs)
        print(f"valeur de retour {value!r}")
        print(f"Fin de {func.__name__}({signature})")           
        return value
    return wrapper_debug
```


```python
@printAppelsFonctions
def fonction1(a):
    c = a + 1
    return c

@printAppelsFonctions
def fonction2(b):
    return fonction1(b+1)

a = fonction2(3)
a
```

    Appel de fonction2(3)
    Appel de fonction1(4)
    valeur de retour 5
    Fin de fonction1(4)
    valeur de retour 5
    Fin de fonction2(3)





    5



**Exemple**

que se passe-t-il dans le cas suivant ?


```python
def fonction1(a):
    fonction1(a)

fonction1(3)
```


```python
@printAppelsFonctions
def fonction1(a):
    fonction1(a)

fonction1(3)
```

## Définition

Un algorithme *récursif* est un algorithme qui fait appel à lui même. Lorsqu'un algorithme n'est pas récursif, on dit qu'il est *itératif*.

Pour éviter une boucle infinie, il faudra impérativement définir **une condition d'arrêt**.

**Exemple**

Le calcul de $n! = n \times (n-1) \times \dots \times 1$. Tout d'abord la version itérative


```python
def factorielleIterative(n):
    r = 1
    for i in range(1,n+1):
        r = r*i
    return r
```


```python
factorielleIterative(3)
```




    6




```python
factorielleIterative(5)
```




    120



La version récursive se base sur le principe suivant :

$n! = \begin{cases}
1 & \text{si } n = 0 \\
n \times (n-1)! & \text{sinon}
\end{cases}$


```python
def factorielleRecursive(n):
    if n == 0:
        return 1
    return n * factorielleRecursive(n-1)
```


```python
factorielleRecursive(3)
```




    6




```python
factorielleRecursive(5)
```




    120



Que se passe-t-il au niveau de la pile ?


```python
@printAppelsFonctions
def factorielleRecursive(n):
    if n == 0:
        return 1
    return n * factorielleRecursive(n-1)

```


```python
factorielleRecursive(3)
```

    Appel de factorielleRecursive(3)
    Appel de factorielleRecursive(2)
    Appel de factorielleRecursive(1)
    Appel de factorielleRecursive(0)
    valeur de retour 1
    Fin de factorielleRecursive(0)
    valeur de retour 1
    Fin de factorielleRecursive(1)
    valeur de retour 2
    Fin de factorielleRecursive(2)
    valeur de retour 6
    Fin de factorielleRecursive(3)





    6



Attention, sur certaines valeurs, on obtient des appels récurisfs à l'infini. Ici, la *fonction termine* sur l'ensemble des entiers positifs mais pas sur les négatifs


```python
factorielleRecursive(-2)
```

## Comment définir une fonction récursive ?

Le principe d'une fonction récursive est assez similaire à la notion de **récurrence** mathématique. On ne cherche pas à calculer le problème dans son ensemble mais simplement à le définir en fonction d'un problème de taille plus petite. Tout comme en mathématique le fait de prouver l'état initial et une seule étape permet de prouver la propriété, dans un algorithme, le fait de calculer l'état initial et une étape permet de calculer n'importe quelle valeur. 

Un algorithme récursif s'écrira toujours de cette façon :
Input : des paramètres
Processus:
    Si les paramètres correspondent à la condition d'arret (cas simple):
        Actions cas d'arret
    Sinon
        Appel(s) récursifs sur de nouveaux paramètres
Pour être sûr que l'algorithme termine, les nouveaux paramètres doivent se rapprocher de la condition d'arrêt.

## Exercices

### Exercice 1

1. Donner un algorithme récursif qui affiche les entiers de 1 à $n$
1. Même chose de $n$ à 1
3. Puis-je modifier ces algorithmes pour qu'ils rajoutent "fin" à la fin de la liste


```python
@printAppelsFonctions
def affiche1n(n):
    if n == 0:
        print("fin")
        return
    affiche1n(n-1)
    print(n)
```


```python
affiche1n(10)
```

    Appel de affiche1n(10)
    Appel de affiche1n(9)
    Appel de affiche1n(8)
    Appel de affiche1n(7)
    Appel de affiche1n(6)
    Appel de affiche1n(5)
    Appel de affiche1n(4)
    Appel de affiche1n(3)
    Appel de affiche1n(2)
    Appel de affiche1n(1)
    Appel de affiche1n(0)
    fin
    valeur de retour None
    Fin de affiche1n(0)
    1
    valeur de retour None
    Fin de affiche1n(1)
    2
    valeur de retour None
    Fin de affiche1n(2)
    3
    valeur de retour None
    Fin de affiche1n(3)
    4
    valeur de retour None
    Fin de affiche1n(4)
    5
    valeur de retour None
    Fin de affiche1n(5)
    6
    valeur de retour None
    Fin de affiche1n(6)
    7
    valeur de retour None
    Fin de affiche1n(7)
    8
    valeur de retour None
    Fin de affiche1n(8)
    9
    valeur de retour None
    Fin de affiche1n(9)
    10
    valeur de retour None
    Fin de affiche1n(10)



```python
def affichen1(n):
    if n == 0:
        print("fin")
        return
    print(n)
    affichen1(n-1)
    
```


```python
affichen1(10)
```

    10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    fin



```python
def concat1n(n):
    if n == 0:
        return ""
    return concat1n(n-1) + " " + str(n) + " fin "
```


```python
concat1n(10)
```




    ' 1 fin  2 fin  3 fin  4 fin  5 fin  6 fin  7 fin  8 fin  9 fin  10 fin '




```python
def concatn1(n):
    if n == 0:
        return ""
    return str(n) + " " + concatn1(n-1)
```


```python
concatn1(10)
```




    '10 9 8 7 6 5 4 3 2 1 '




```python

```

### Exercice 2

Pour chacun des algorithmes suivants :

1. Déterminez pour quelles valeurs d'entrée l'algorithme termine (= ne fait pas de boucles infinies)
2. Calculez un exemple à la main
3. Expliquez ce que calcule l'algorithme


```python
def fonction1(n):
    if n == 0:
        return 1
    return fonction1(n+1)
```

La fonction va terminer sur les valeurs négatives et renvoie toujours 1
Boucle infinie sur les strictements positifs



```python
fonction1(-6)
```




    1




```python
def fonction2(n):
    if n == 0:
        return 0
    return fonction2(n-1)+n
```

Termine pour les nombres positifs (boucle infinie sur les strictement négatifs)
Calcule la somme des nombres de 1 à n


```python
fonction2(5)
```




    15




```python
def fonction3(n):
    if n == 0:
        return 0
    return fonction3(n-1) - n
```

Termine pour les nombres positifs (boucle infinie sur les strictement négatifs)
Calcule -(la somme des nombres de 1 à n)


```python
fonction3(5)
```




    -15




```python
def fonction4(n):
    if n == 0:
        return 0
    if n < 0:
        return n + fonction4(-n)
    return n + fonction4(-n+1)
```

Termine pour tous les entiers
Calcule pour les positifs :

exemple 5

$5 + -4 + 4 + -3 + 3 + -2 + 2 + -1 + 1 + 0 = 5$

Pour les négatifs : 0


```python
fonction4(-10)
```




    0




```python
def fonction5(n):
    if n <= 1:
        return 0
    return 1 + fonction5(n-2)
```

Termine pour tous les entiers 

Calcule n//2


```python
fonction5(11)
```




    5



### Exercice 3

La fonction de fibonacci est définie par :

$U_0 = 1$

$U_1 = 1$

$U_n = U_{n-1} + U_{n-2}$ si $n \geq 2$

Ces premières valeurs sont donc : 1, 1, 2, 3, 5, 8, 13, ...

Donner deux algorithmes, un itératif et un récursif, qui calculent la valeur $n$ de la suite.



```python
def fiboIteratif(n):
    u0 = 1
    u1 = 1
    for i in range(2,n+1):
        u0, u1 = u1, u0 + u1
    return u1
```


```python
[fiboIteratif(i) for i in range(10)]
```




    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]




```python
def fiboRec(n):
    if n <= 1:
        return 1
    return fiboRec(n-1) + fiboRec(n-2)
```


```python
fiboRec(5)
```




    8




```python
[fiboRec(i) for i in range(10)]
```




    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]



### Exercice 4

On rappelle sur un exemple le principe de l'algorithme d'Euclide du calcul du pgcd (plus grand diviseur commun). 

Calcul du pgcd de 2145 et 630 : On commence par effectuer la division euclidienne de 2145 par 630

$2145 = 630 * 3 + 255$

puis on effectue la division de 630 par le reste obtenu 255

$630 = 255 * 2 + 120$

On continue jusqu'à ce que l'on trouve un reste nul.

$\begin{align*}
255 &= 120 *2 + 15 \\
120 &= 15 * 8
\end{align*}$

Le pgcd est le dernier reste non nul, c'est-à-dire **15**.

Donner un algorithme récursif qui calcule le pgcd de deux nombres.


```python

```


```python

```


```python

```

### Exercice 5

Reprendre l'algorithme de recherche dichotomique dans un tableau trié vu dans le TD1 et donner une version récursive.


```python
T = [1,2,3,3,4]
T
```




    [1, 2, 3, 3, 4]




```python
T[0]
```




    1




```python
len(T)
```




    5




```python
def dicho(T, deb, fin, x):
    if deb == fin:
        return False
    m = (deb + fin)//2
    if x == T[m]:
        return True
    if x < T[m]:
        return dicho(T,deb,m,x)
    return dicho(T,m+1,fin,x)
```


```python
T = [1,2,3,3,4]
dicho(T,0,len(T),2)
```




    True




```python
dicho(T,0,len(T),3.5)
```




    False




```python
dicho(T,0,len(T),6)
```




    False




```python
dicho(T,0,len(T),-3)
```




    False



### Exemple avancé : les Tours de Hanoï



Problème : on possède trois pics sur lesquels sont empilés des disques de tailles décroissantes (tous sur le premier pic). On souhaite déplacer la pile sur le second pic en suivant les règles suivantes:

* on ne peut déplacer qu'un seul disque à la fois, celui du haut de la pile,
* on ne peut poser un disque que sur un disque plus grand.


On suppose donc que l'on dispose d'une seule action possible :
Fonction Déplacer
Input : 
    - le pic de départ
    - le pic d'arrivée
Processus :
    Si départ n'est pas vide:
        D <- disque retiré au sommet de départ
    Sinon:
        Erreur "Départ est vide"
    Si D < disque au sommet d'arrivée:
        Poser D au sommet d'arrivée
    Sinon:
        Erreur "Action impossible"
En python, on utilisera l'interface suivante :


```python
class Towers:
    
    def __init__(self,n):
        self.towers = (list(range(n,0,-1)),[],[])
        self.size = n
    
    def move(self,i,j):
        t1,t2 = self.towers[i], self.towers[j]
        if len(t1) == 0 or (len(t2) != 0 and t1[-1]>t2[-1]):
            raise ValueError("Invalid action")
        print("Move from Tower " + str(i) + " to Tower " + str(j))
        t2.append(t1.pop())
    
    def __repr__(self):
        res = ""
        n = self.size
        for i in range(n):
            line = ""
            for t in self.towers:
                if len(t) > i:
                    v = t[i]
                else:
                    v = 0
                stars = v*"*"
                spaces = (n-v)*" "
                line+= spaces + stars + "|" + stars + spaces + " "
            line+="\n"
            res = line + res
        return res
```


```python
T = Towers(3)
T
```




      *|*      |       |    
     **|**     |       |    
    ***|***    |       |    




```python
T.move(0,1)
T
```

    Move from Tower 0 to Tower 1





       |       |       |    
     **|**     |       |    
    ***|***   *|*      |    




```python
T.move(0,2)
T
```

    Move from Tower 0 to Tower 2





       |       |       |    
       |       |       |    
    ***|***   *|*    **|**  




```python
T.move(1,2)
T
```

    Move from Tower 1 to Tower 2





       |       |       |    
       |       |      *|*   
    ***|***    |     **|**  




```python
T.move(0,1)
T
```

    Move from Tower 0 to Tower 1





       |       |       |    
       |       |      *|*   
       |    ***|***  **|**  




```python
T.move(2,0)
T
```

    Move from Tower 2 to Tower 0





       |       |       |    
       |       |       |    
      *|*   ***|***  **|**  




```python
T.move(2,1)
T
```

    Move from Tower 2 to Tower 1





       |       |       |    
       |     **|**     |    
      *|*   ***|***    |    




```python
T.move(0,1)
T
```

    Move from Tower 0 to Tower 1





       |      *|*      |    
       |     **|**     |    
       |    ***|***    |    




```python

```


```python

```

**Comment résoudre le problème ?**

Pour résoudre un problème de façon récursive, il faut répondre à plusieurs questions :

1. Quelle est la taille de mon problème ?
2. Quelle est la plus petite taille possible ? (condition d'arrêt)
3. Comment résoudre le problème dans ce cas là ? (action d'arrêt)
4. Si je suppose que je sais résoudre le problème pour toutes les tailles $k < n$, comment le résoudre pour la taille $n$ ?



```python
@compteAppels
def hanoi(T,n,dep, arrivee, inter):
    if n == 1:
        T.move(dep,arrivee)
        print(T)
    else:
        hanoi(T,n-1,dep,inter,arrivee)
        T.move(dep,arrivee)
        print(T)
        hanoi(T,n-1,inter,arrivee,dep)
```


```python
hanoi(Towers(3),3,0,1,2)
```

    Move from Tower 0 to Tower 1
       |       |       |    
     **|**     |       |    
    ***|***   *|*      |    
    
    Move from Tower 0 to Tower 2
       |       |       |    
       |       |       |    
    ***|***   *|*    **|**  
    
    Move from Tower 1 to Tower 2
       |       |       |    
       |       |      *|*   
    ***|***    |     **|**  
    
    Move from Tower 0 to Tower 1
       |       |       |    
       |       |      *|*   
       |    ***|***  **|**  
    
    Move from Tower 2 to Tower 0
       |       |       |    
       |       |       |    
      *|*   ***|***  **|**  
    
    Move from Tower 2 to Tower 1
       |       |       |    
       |     **|**     |    
      *|*   ***|***    |    
    
    Move from Tower 0 to Tower 1
       |      *|*      |    
       |     **|**     |    
       |    ***|***    |    
    
    7 appels à la fonction hanoi



```python

```


```python

```

## Complexité d'un algorithme récursif

### méthode de calcul

Reprenons le schéma de base d'un algorithme récursif  que l'on précise légèrement:
Fonction R
Input : des paramètres
Processus:
    Si les paramètres correspondent à la condition d'arret (cas simple):
        Actions cas d'arret
    Sinon
        Actions itératives et 
        k Appel(s) récursifs: R(p1), R(p2), ..., R(pk)
On veut compter le nombre d'actions de base. Chaque appel de fonction est une action de base. Soit $f$ la complexité de l'algorithme. Pour simplifier l'écriture, on suppose que les paramètres de l'algorithme correspondent à la taille $n$ du problème. La condition d'arrêt est obtenue quand $n=0$ et correspond à une complexité constante $c_0$. On obtient une définition récursive de $f$

$\begin{align}
f(0) &= c_0 \\
f(n) &= g(n) + \sum_{i=0}^k f(p_i)
\end{align}$

où $g$ est la complexité de la partie itérative. La complexité dépend donc du **nombre d'appels récursifs** à chaque étape et de la **taille des paramètres**. Il peut être plus ou moins simple de *développer* la fonction $f$ pour obtenir une formule close (non récursive).

### Cas classiques

On va regarder quelques cas classiques et compter le nombre d'appels de fonction. Pour cela, on utilise la fonctionnalité suivante (exécuter la cellule)


```python
import functools

COMPTEUR = 0
STACK = 0

def compteAppels(func):
    c = 0
    """Print the function signature and return value"""
    @functools.wraps(func)
    def wrapper_debug(*args, **kwargs):
        global COMPTEUR, STACK
        COMPTEUR +=1
        STACK += 1
        value = func(*args, **kwargs)
        STACK -=1
        if STACK == 0:
            print(f"{COMPTEUR} appels à la fonction {func.__name__}")
            COMPTEUR = 0
        return value
    return wrapper_debug
```

**Exemple : cas linéaire**

On reprend la fonction factorielle vue précédemment.


```python
@compteAppels
def factorielle(n):
    if n <= 0:
        return 1
    return n*factorielle(n-1)
```


```python
factorielle(10)
```

    11 appels à la fonction factorielle





    3628800



Lorsqu'on appelle `factorielle(n)` on génère $n+1$ appels de fonctions. On est sur le schéma suivant :
Fonction R
Input : un entier n
Processus:
    Si n=0:
        Actions cas d'arret
    Sinon
        Appel de R(n-1)
Dans ce cas, si $f$ est le nombre d'appels, on a 

$\begin{align}
f(0) &= 1 \\
f(n) &= 1 + f(n-1)
\end{align}$

Lorsqu'on développe, on obtient

$\begin{equation}
f(n) = 1 + 1 + 1 + \dots + 1 = n+1
\end{equation}$

$n+1$ fois.

Conclusion : la complexité est en $O(n)$.

**Exemple : cas exponentiel**

Reprenons l'exemple des Tours de Hanoï. Combien d'appels de fonctions sont réalisés pour la taille $n$ ?


```python
@compteAppels
def Hanoi(n, T, depart, arrivee, inter):
    if n == 0:
        return
    Hanoi(n-1, T, depart, inter, arrivee)
    T.move(depart, arrivee)
    Hanoi(n-1, T, inter, arrivee, depart)
```


```python
n = 3
T = Towers(n)
Hanoi(n,T,0,1,2)
T
```

    Move from Tower 0 to Tower 1
    Move from Tower 0 to Tower 2
    Move from Tower 1 to Tower 2
    Move from Tower 0 to Tower 1
    Move from Tower 2 to Tower 0
    Move from Tower 2 to Tower 1
    Move from Tower 0 to Tower 1
    15 appels à la fonction Hanoi





       |      *|*      |    
       |     **|**     |    
       |    ***|***    |    



On est sur le schéma suivant :
Fonction R
Input : un entier n
Processus:
    Si n=0:
        Actions cas d'arret
    Sinon:
        2 appels de R(n-1)
Dans ce cas, la complexité est donnée par le nombre d'appels $f$ avec

$\begin{align}
f(0) &= 1 \\
f(n) &= 1 + 2 \times f(n-1).
\end{align}$

Par exemple, pour $n=3$ :

$\begin{align}
f(3) &= 1 + 2f(2) = 1 + 2(1 + 2f(1)) = 1 + 2(1 + 2(1 + 2))\\
 &= 15 = 2^4 - 1.
\end{align}$

On prouve facilement par récurrence que
$\begin{equation}
f(n) = 2^{n+1} - 1.
\end{equation}$

En effet, $f(0) = 1 = 2^1 - 1$ et si on suppose la formule vraie pour $n$, on obtient pour $n+1$

$f(n+1) = 1 + 2 f(n) = 1 + 2(2^{n+1} -1) = 1 + 2^{n+2} - 2 = 2^{n+2} - 1$

On est dans le cas d'une complexité exponentielle en $O(2^n)$.

**Exemple : cas logarithmique**

Reprenons l'exemple de la fonction de recherche dichotomique. Combien d'appels sont réalisés ici ?


```python
@compteAppels
def rechercheDich(T,v,deb, fin):
    m = (deb+fin)//2
    if deb == fin:
        return False
    if T[m] == v:
        return True
    if v < T[m]:
        return rechercheDich(T,v,deb,m)
    return rechercheDich(T,v,m+1,fin)
```


```python
n = 10000000
T = list(range(n))
v = 0.5
rechercheDich(T,v,0,n)
```

    25 appels à la fonction rechercheDich





    False



On est sur le schéma suivant
Fonction R
Input : un entier n
Processus:
    Si n=0:
        Actions cas d'arret
    Sinon:
        Appel de R(n/2)
Dans ce cas, si $f$ est le nombre d'appels, on a

$\begin{align}
f(0) &= 1 \\
f(n) &= 1 + f(\lfloor n/2 \rfloor).
\end{align}$

Développons sur un exemple :

$\begin{align}
f(10) &= 1 + f(5) = 2 + f(2) = 3 + f(1) = 5 \\
&= \log(10) + 2.
\end{align}$

(on prend le $\log$ en base 2)

On prouve par récurrence
$\begin{equation}
f(n) = \lfloor \log(n) \rfloor + 2.
\end{equation}$

En effet, 

$f(1) = 1 + f(0) = 2 = \log(1) + 2$ 

En supposant la formule correcte pour toute valeur inférieure stricte à $n$, on obtient

$\begin{align}
f(n) &= 1 + f(\lfloor n/2 \rfloor) \\
&= 1 + \lfloor \log(\lfloor  n/2 \rfloor) \rfloor + 2
\end{align}$

Supposons $n$ pair, si $k = \lfloor \log(n/2) \rfloor$, cela signifie

$2^k \leq \frac{n}{2} < 2^{k+1}$, c'est à dire

$2^{k+1} \leq n < 2^{k+2}$

On peut obtenir une inégalité similaire dans le cas de $n$ impair. Cela signifie que :

$\lfloor \log(\lfloor  n/2 \rfloor) \rfloor = \lfloor \log(n) \rfloor - 1$ 

et donc

$f(n) = 1 + \lfloor \log(n) \rfloor - 1 + 2 = \lfloor \log(n) \rfloor + 2$

On a donc une complexité en $O(log(n))$.

### Conclusion : calcul de complexité

Si l'on simplifie le problème aux cas où la partie itérative de la fonction est en $O(1)$ (comme dans les exemples précédents). La complexité est donnée entièrement par le nombre d'appels récursifs, $f$ on a 3 cas de figures. ($v \geq 1$ et $k \geq 2$ sont des constantes qui ne dépendent pas de $n$)

$f(n) =  1 + f(n-v) \rightarrow$ complexité linéaire $O(n)$

$f(n) = 1 + k f(n - v) \rightarrow$ complexité exponentielle $O(k^n)$

$f(n) = 1 + f(n/k) \rightarrow$ complexité logarithmique $O(\log(n))$ (la constante $k$ agit sur la base dans laquelle on prend le logarithme, ce qui ne change pas la classe de complexité)

## Exercices

### Exercice 6

Dans la fonction suivante du calcul des nombres de Fibonacci, combien d'appels de fonctions sont réalisés pour un $n$ donné ? Quelle est la complexité ?


```python
@compteAppels
def fibo(n):
    if n <= 1:
        return 1
    return fibo(n-1) + fibo(n-2)
```

Le nombre d'appels est donné par

$f(0) = f(1) = 1$

$f(n) = 1 + f(n-1) + f(n-2)$


```python
fibo(20)
```

    21891 appels à la fonction fibo





    10946




```python
def fiboIteratif(n):
    u0 = 1
    u1 = 1
    for i in range(2,n+1):
        u0, u1 = u1, u0 + u1
    return u1
```


```python
fiboIteratif(100)
```




    573147844013817084101




```python

```


```python

```

### Exercice 7

Il existe deux définitions récursives de la fonction puissance :

$\begin{align*}
a^b &= \begin{cases}
1 &\text{si }b=0 \\
a \times a^{b-1} &\text{sinon}
\end{cases} \\
a^b &= \begin{cases}
1 &\text{si }b=0 \\
a \times a^{b-1} &\text{si }b\text{ est impair} \\
a^{\frac{b}{2}}a^{\frac{b}{2}} &\text{si }b\text{ est pair}
\end{cases}
\end{align*}$

Pour chacune des définitions, donner l'algorithme récursif correspondant ainsi que sa complexité.


```python
@compteAppels
def puissance1(a,b):
    if b == 0:
        return 1
    return a * puissance1(a,b-1)
```


```python
puissance1(2,100)
```

    101 appels à la fonction puissance1





    1267650600228229401496703205376




```python
@compteAppels
def puissance2(a,b):
    if b == 0:
        return 1
    if b%2 == 1:
        res = puissance2(a,(b-1)//2)
        return a * res * res
    res = puissance2(a,b//2)
    return res * res
    #return puissance2(a,b//2) * puissance2(a,b//2)
```


```python
puissance2(2,10000)
```

    15 appels à la fonction puissance2





    19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376



## Pour finir : itératif ou récursif ?

En terme de complexité, la récursivité ne permet pas par défaut d'obtenir des algorithmes plus efficaces. Quand elle est mal utilisée, elle peut même donner des complexité **plus mauvaise** : exemple de Fibonacci. Par ailleurs, on peut prouver qu'il existe **toujours** une version itérative d'un algorithme récursif : il suffit de déplier la pile !

**Qu'en est-il de la complexité mémoire ?** Reprendre l'exemple de la fonction exponentielle en itératif et en récursif. La complexité mémoire de l'algorithme récursif est en $O(n)$ tandis qu'il est en $O(1)$ pour l'itératif.

**Alors pourquoi on fait du récursif ?** Sur de nombreux problèmes, les algorithmes récursifs sont beaucoup plus simples à concevoir que les algorithmes itératifs. C'est le cas de l'algorithme des Tour de Hanoi. Ils donnent des codes plus courts et plus lisibles. Par ailleurs, certaines **structure de données** ont elles-mêmes des **définition récursives** et sont particulièrement adaptés aux algorithmes récursifs : les arbres, les graphes, les listes chaînées. 


```python

```

294ec0a2db4506c0bfdb68332398956870e97f4e
ipynb
Jupyter Notebook
Algorithmic_Polytech/3-Recursivite/cours-recursivite.ipynb
VivianePons/courses
5f1d6ce80efff97129bf8c723394acec65283563
CC-BY-4.0
2016-09-02T17:31:59.000Z
2021-05-25T12:54:46.000Z
Algorithmic_Polytech/3-Recursivite/cours-recursivite.ipynb
VivianePons/courses
5f1d6ce80efff97129bf8c723394acec65283563
CC-BY-4.0
2016-09-07T17:00:10.000Z
2016-09-09T07:23:02.000Z
Algorithmic_Polytech/3-Recursivite/cours-recursivite.ipynb
VivianePons/courses
5f1d6ce80efff97129bf8c723394acec65283563
CC-BY-4.0
2018-01-21T19:55:41.000Z
2019-10-15T14:08:53.000Z
Qwen/Qwen-72B
1. YES
2. YES