# Exercices sur la récursivité et la programmation dynamique

## Évolution des abonnements

Un youtuber constate chaque mois qu'il recrute 3000 nouveaux abonnés mais dans le même temps la lassitude pousse 2% de ses fidèles à se désabonner. Ce mois-ci (n=0) il compte 100000 abonnés et il souhaite pouvoir calculer les prédictions de ses abonnés pour démarcher des sponsors dans les mois à venir. Écrivez récursivement la fonction `prev_abo` qui calcule le nombre d'abonné au mois n.

Utilisez votre fonction `prev_abo` pour calculer le nombre d'abonnés dans les mois à venir.

D'après vous, le youtuber peut-il prétendre à ces sponsors qu'il va bientôt atteindre les 200000 abonnés ? Utilisez votre programme pour constater l'évolution des abonnés à long terme.


```python
def prev_abo(n:int) -> float:
    """ n must be >= 0 """
    un = 100000
    if n > 0 :
        un = 0.98 * prev_abo(n-1) + 3000
    return un

for n in range(0,200):
    print(prev_abo(n))
```

    100000
    101000.0
    101980.0
    102940.4
    103881.59199999999
    104803.96015999999
    105707.88095679999
    106593.72333766398
    107461.84887091069
    108312.61189349247
    109146.35965562263
    109963.43246251017
    110764.16381325996
    111548.88053699477
    112317.90292625487
    113071.54486772977
    113810.11397037517
    114533.91169096767
    115243.23345714831
    115938.36878800533
    116619.60141224522
    117287.2093840003
    117941.46519632029
    118582.63589239388
    119210.983174546
    119826.76351105508
    120430.22824083397
    121021.62367601729
    121601.19120249695
    122169.167378447
    122725.78403087806
    123271.26835026049
    123805.84298325528
    124329.72612359017
    124843.13160111837
    125346.268969096
    125839.34358971407
    126322.5567179198
    126796.1055835614
    127260.18347189017
    127714.97980245236
    128160.68020640331
    128597.46660227524
    129025.51727022973
    129445.00692482512
    129856.10678632862
    130258.98465060204
    130653.80495759
    131040.72885843819
    131419.91428126942
    131791.51599564403
    132155.68567573116
    132512.57196221652
    132862.3205229722
    133205.07411251275
    133540.9726302625
    133870.15317765722
    134192.75011410407
    134508.895111822
    134818.71720958556
    135122.34286539385
    135419.89600808595
    135711.49808792424
    135997.26812616576
    136277.32276364244
    136551.7763083696
    136820.7407822022
    137084.32596655816
    137342.639447227
    137595.78665828245
    137843.8709251168
    138086.99350661444
    138325.25363648214
    138558.7485637525
    138787.57359247745
    139011.82212062788
    139231.5856782153
    139446.953964651
    139658.014885358
    139864.85458765083
    140067.5574958978
    140266.20634597985
    140460.88221906027
    140651.66457467905
    140838.63128318547
    141021.85865752175
    141201.4214843713
    141377.39305468387
    141549.84519359018
    141718.8482897184
    141884.47132392402
    142046.78189744553
    142205.8462594966
    142361.72933430667
    142514.49474762054
    142664.20485266813
    142810.92075561476
    142954.70234050247
    143095.6082936924
    143233.69612781855
    143369.02220526218
    143501.64176115693
    143631.6089259338
    143758.97674741512
    143883.7972124668
    144006.12126821745
    144125.9988428531
    144243.47886599603
    144358.60928867612
    144471.4371029026
    144582.00836084454
    144690.36819362766
    144796.5608297551
    144900.62961315998
    145002.61702089678
    145102.56468047886
    145200.51338686928
    145296.5031191319
    145390.57305674927
    145482.76159561428
    145573.10636370198
    145661.64423642794
    145748.41135169938
    145833.44312466538
    145916.77426217208
    145998.43877692864
    146078.47000139006
    146156.90060136226
    146233.762589335
    146309.0873375483
    146382.9055907973
    146455.24747898136
    146526.14252940172
    146595.61967881367
    146663.7072852374
    146730.43313953266
    146795.824476742
    146859.90798720717
    146922.70982746303
    146984.25563091377
    147044.57051829548
    147103.67910792958
    147161.60552577098
    147218.37341525557
    147274.00594695046
    147328.52582801145
    147381.95531145122
    147434.3162052222
    147485.62988111775
    147535.9172834954
    147585.19893782548
    147633.49495906898
    147680.8250598876
    147727.20855868986
    147772.66438751607
    147817.21109976573
    147860.8668777704
    147903.649540215
    147945.5765494107
    147986.6650184225
    148026.93171805405
    148066.39308369296
    148105.0652220191
    148142.96391757872
    148180.10463922715
    148216.5025464426
    148252.17249551375
    148287.12904560348
    148321.3864646914
    148354.95873539758
    148387.85956068963
    148420.10236947582
    148451.7003220863
    148482.66631564457
    148513.01298933168
    148542.75272954503
    148571.89767495412
    148600.45972145503
    148628.45052702594
    148655.88151648542
    148682.7638861557
    148709.10860843258
    148734.92643626392
    148760.22790753865
    148785.02334938786
    148809.3228824001
    148833.1364247521
    148856.47369625705
    148879.3442223319
    148901.75733788527
    148923.72219112757
    148945.24774730502
    148966.34279235892
    148987.01593651174
    149007.2756177815
    149027.13010542587
    149046.58750331734
    149065.655753251
    149084.34263818598
    149102.65578542225


## Sans maitrise la puissance n'est rien

Écrivez par récurence une function `puissance(x: float, n: int) -> float` qui calcule $x^n$ pour n >= 0 en utilisant uniquement des multiplications et la valeur de $x^0$.


```python
def puissance(x:float, n:int) -> float:
    """ n must be >= 0
    >>> puissance(0,0)
    1
    >>> puissance(1,0)
    1
    >>> puissance(1,1)
    1
    >>> puissance(1,3)
    1
    >>> puissance(2,3)
    8
    >>> puissance(10,5)
    100000
    """
    result = 1
    if n > 0:
        result = x * puissance(x, n-1)
    return result

import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)
```




    TestResults(failed=0, attempted=6)



## Un PGCD pour l'examen ?

Calculons le PGCD avec l'algorithme d'Euclide qui dit ceci :
- Le pgcd de a et b (entiers > 0) est le même que le pgcd de b et c avec c qui est le reste de la division entière (en python le modulo  :**%**) de a par b. 
- Le pgcd de a par 0 est a


```python
def pgcd(a:int, b:int) -> int:
    """ return highest common factor
        a must be > 0 """
    assert a > 0, "a must be > 0"
    if b == 0: return a
    else:
        return pgcd(b, a%b)
    
pgcd(12,8)
```




    4



## Réduction de fraction

Utiliser le pgcd précédent pour écrire une fonction qui réduit les fractions entières comme ceci : `reduc(12,4)` retourne `(3,1)` car $\dfrac{12}{8} = \dfrac{3}{2}$.


```python
def reduc(a:int, b:int):
    return (a//pgcd(a,b), b//pgcd(a,b))

reduc(12,8)
```




    (3, 2)



## Suite de Syracuse

Programmez par **récursivité** la [suite de Syracuse](https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse#Suite_de_Syracuse) définie **pour des entiers** comme ceci :

$u_o = N$ avec N entier > 0

$u_{n+1}={\begin{cases}{\dfrac {u_{n}}{2}} \; {\mbox{si }}u_{n}{\mbox{ est pair,}}\\3u_{n}+1 \; {\mbox{si }}u_{n}{\mbox{ est impair.}}\end{cases}}$

💡 **Si vous appelez récursivement plusieurs fois la fonction avec les mêmes paramètres, il vaut mieux faire 1 seul appel et mettre le résultat dans une variable. Vous limiterez ainsi considérablement le nombre d'appels.**


```python
def syracuse_noob(u0: int, n: int) -> int:
    """ Return Syracuse suite value
    u0 must be > 0 ; n must be >= 0
    >>> syracuse_noob(1, 0)
    1
    >>> syracuse_noob(15, 7)
    160
    >>> syracuse_noob(15, 4)
    35
    >>> syracuse_noob(15, 17)
    1
    """
    if n <= 0: return u0
    elif syracuse_noob(u0, n-1) % 2 == 0: return syracuse_noob(u0, n-1) // 2
    else: return 3*syracuse_noob(u0, n-1)+1
    return result

def syracuse(u0: int, n: int) -> int:
    """ Return Syracuse suite value
    u0 must be > 0 ; n must be >= 0
    >>> syracuse(1, 0)
    1
    >>> syracuse(15, 7)
    160
    >>> syracuse(15, 4)
    35
    >>> syracuse(15, 17)
    1
    """
    result = u0
    if n > 0:
        u_n_moins_1 = syracuse(u0, n-1)
        if u_n_moins_1 % 2 == 0: result = u_n_moins_1 // 2
        else: result = 3*u_n_moins_1+1
    return result

import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)
```




    TestResults(failed=0, attempted=14)



Pour l'appel de la fonction `syracuse(15, 3)` comptez au brouillon combien de fois la fonction `syracuse` se lance en écrivant l'arbre des appels.

Vérifiez cela en modifiant votre programme, puis trouvez le nombre d'appel pour calculer `syracuse(15, 5)`, `syracuse(15, 10)`, `syracuse(15, 15)` et `syracuse(15, 20)`. Que pensez vous de ces derniers résultats ?


```python
def syracuse_noob(u0: int, n: int) -> int:
    """ Return Syracuse suite value
    u0 must be > 0 ; n must be >= 0 """
    global compteur
    compteur += 1
    if n <= 0: return u0
    elif syracuse_noob(u0, n-1) % 2 == 0: return syracuse_noob(u0, n-1) // 2
    else: return 3*syracuse_noob(u0, n-1)+1
    return result

def syracuse(u0: int, n: int) -> int:
    """ Return Syracuse suite value
    u0 must be > 0 ; n must be >= 0 """
    global compteur
    compteur += 1
    result = u0
    if n > 0:
        u_n_moins_1 = syracuse(u0, n-1)
        if u_n_moins_1%2 == 0: result = u_n_moins_1//2
        else: result = 3*u_n_moins_1+1
    return result

compteur = 0
syracuse_noob(15, 20)
print(compteur)

compteur = 0
syracuse(15, 20)
print(compteur)
```

    2097151
    21


Une conjecture encore non démontrée en mathématique affirme que pour tout N entier > 0 il existe toujours un terme de la suite pour lequel $u_n = 1$.

Écrivez un programme qui montre cette conjecture pour les valeurs de N allant jusqu'à 30.


```python
def syracuse(u0: int, n: int) -> int:
    """ Return Syracuse suite value
    u0 must be > 0 ; n must be >= 0 """
    result = u0
    if n > 0:
        u_n_moins_1 = syracuse(u0, n-1)
        if u_n_moins_1%2 == 0: result = u_n_moins_1//2
        else: result = 3*u_n_moins_1+1
    return result

for u0 in range(1,31):
    n = 0
    while syracuse(u0,n) != 1:
        print(f"On cherche pour N={u0} au rang n={n}")
        n += 1
    print(f"Pour N={u0} un=1 au rang n={n}")
```

    Pour N=1 un=1 au rang n=0
    On cherche pour N=2 au rang n=0
    Pour N=2 un=1 au rang n=1
    On cherche pour N=3 au rang n=0
    On cherche pour N=3 au rang n=1
    On cherche pour N=3 au rang n=2
    On cherche pour N=3 au rang n=3
    On cherche pour N=3 au rang n=4
    On cherche pour N=3 au rang n=5
    On cherche pour N=3 au rang n=6
    Pour N=3 un=1 au rang n=7
    On cherche pour N=4 au rang n=0
    On cherche pour N=4 au rang n=1
    Pour N=4 un=1 au rang n=2
    On cherche pour N=5 au rang n=0
    On cherche pour N=5 au rang n=1
    On cherche pour N=5 au rang n=2
    On cherche pour N=5 au rang n=3
    On cherche pour N=5 au rang n=4
    Pour N=5 un=1 au rang n=5
    On cherche pour N=6 au rang n=0
    On cherche pour N=6 au rang n=1
    On cherche pour N=6 au rang n=2
    On cherche pour N=6 au rang n=3
    On cherche pour N=6 au rang n=4
    On cherche pour N=6 au rang n=5
    On cherche pour N=6 au rang n=6
    On cherche pour N=6 au rang n=7
    Pour N=6 un=1 au rang n=8
    On cherche pour N=7 au rang n=0
    On cherche pour N=7 au rang n=1
    On cherche pour N=7 au rang n=2
    On cherche pour N=7 au rang n=3
    On cherche pour N=7 au rang n=4
    On cherche pour N=7 au rang n=5
    On cherche pour N=7 au rang n=6
    On cherche pour N=7 au rang n=7
    On cherche pour N=7 au rang n=8
    On cherche pour N=7 au rang n=9
    On cherche pour N=7 au rang n=10
    On cherche pour N=7 au rang n=11
    On cherche pour N=7 au rang n=12
    On cherche pour N=7 au rang n=13
    On cherche pour N=7 au rang n=14
    On cherche pour N=7 au rang n=15
    Pour N=7 un=1 au rang n=16
    On cherche pour N=8 au rang n=0
    On cherche pour N=8 au rang n=1
    On cherche pour N=8 au rang n=2
    Pour N=8 un=1 au rang n=3
    On cherche pour N=9 au rang n=0
    On cherche pour N=9 au rang n=1
    On cherche pour N=9 au rang n=2
    On cherche pour N=9 au rang n=3
    On cherche pour N=9 au rang n=4
    On cherche pour N=9 au rang n=5
    On cherche pour N=9 au rang n=6
    On cherche pour N=9 au rang n=7
    On cherche pour N=9 au rang n=8
    On cherche pour N=9 au rang n=9
    On cherche pour N=9 au rang n=10
    On cherche pour N=9 au rang n=11
    On cherche pour N=9 au rang n=12
    On cherche pour N=9 au rang n=13
    On cherche pour N=9 au rang n=14
    On cherche pour N=9 au rang n=15
    On cherche pour N=9 au rang n=16
    On cherche pour N=9 au rang n=17
    On cherche pour N=9 au rang n=18
    Pour N=9 un=1 au rang n=19
    On cherche pour N=10 au rang n=0
    On cherche pour N=10 au rang n=1
    On cherche pour N=10 au rang n=2
    On cherche pour N=10 au rang n=3
    On cherche pour N=10 au rang n=4
    On cherche pour N=10 au rang n=5
    Pour N=10 un=1 au rang n=6
    On cherche pour N=11 au rang n=0
    On cherche pour N=11 au rang n=1
    On cherche pour N=11 au rang n=2
    On cherche pour N=11 au rang n=3
    On cherche pour N=11 au rang n=4
    On cherche pour N=11 au rang n=5
    On cherche pour N=11 au rang n=6
    On cherche pour N=11 au rang n=7
    On cherche pour N=11 au rang n=8
    On cherche pour N=11 au rang n=9
    On cherche pour N=11 au rang n=10
    On cherche pour N=11 au rang n=11
    On cherche pour N=11 au rang n=12
    On cherche pour N=11 au rang n=13
    Pour N=11 un=1 au rang n=14
    On cherche pour N=12 au rang n=0
    On cherche pour N=12 au rang n=1
    On cherche pour N=12 au rang n=2
    On cherche pour N=12 au rang n=3
    On cherche pour N=12 au rang n=4
    On cherche pour N=12 au rang n=5
    On cherche pour N=12 au rang n=6
    On cherche pour N=12 au rang n=7
    On cherche pour N=12 au rang n=8
    Pour N=12 un=1 au rang n=9
    On cherche pour N=13 au rang n=0
    On cherche pour N=13 au rang n=1
    On cherche pour N=13 au rang n=2
    On cherche pour N=13 au rang n=3
    On cherche pour N=13 au rang n=4
    On cherche pour N=13 au rang n=5
    On cherche pour N=13 au rang n=6
    On cherche pour N=13 au rang n=7
    On cherche pour N=13 au rang n=8
    Pour N=13 un=1 au rang n=9
    On cherche pour N=14 au rang n=0
    On cherche pour N=14 au rang n=1
    On cherche pour N=14 au rang n=2
    On cherche pour N=14 au rang n=3
    On cherche pour N=14 au rang n=4
    On cherche pour N=14 au rang n=5
    On cherche pour N=14 au rang n=6
    On cherche pour N=14 au rang n=7
    On cherche pour N=14 au rang n=8
    On cherche pour N=14 au rang n=9
    On cherche pour N=14 au rang n=10
    On cherche pour N=14 au rang n=11
    On cherche pour N=14 au rang n=12
    On cherche pour N=14 au rang n=13
    On cherche pour N=14 au rang n=14
    On cherche pour N=14 au rang n=15
    On cherche pour N=14 au rang n=16
    Pour N=14 un=1 au rang n=17
    On cherche pour N=15 au rang n=0
    On cherche pour N=15 au rang n=1
    On cherche pour N=15 au rang n=2
    On cherche pour N=15 au rang n=3
    On cherche pour N=15 au rang n=4
    On cherche pour N=15 au rang n=5
    On cherche pour N=15 au rang n=6
    On cherche pour N=15 au rang n=7
    On cherche pour N=15 au rang n=8
    On cherche pour N=15 au rang n=9
    On cherche pour N=15 au rang n=10
    On cherche pour N=15 au rang n=11
    On cherche pour N=15 au rang n=12
    On cherche pour N=15 au rang n=13
    On cherche pour N=15 au rang n=14
    On cherche pour N=15 au rang n=15
    On cherche pour N=15 au rang n=16
    Pour N=15 un=1 au rang n=17
    On cherche pour N=16 au rang n=0
    On cherche pour N=16 au rang n=1
    On cherche pour N=16 au rang n=2
    On cherche pour N=16 au rang n=3
    Pour N=16 un=1 au rang n=4
    On cherche pour N=17 au rang n=0
    On cherche pour N=17 au rang n=1
    On cherche pour N=17 au rang n=2
    On cherche pour N=17 au rang n=3
    On cherche pour N=17 au rang n=4
    On cherche pour N=17 au rang n=5
    On cherche pour N=17 au rang n=6
    On cherche pour N=17 au rang n=7
    On cherche pour N=17 au rang n=8
    On cherche pour N=17 au rang n=9
    On cherche pour N=17 au rang n=10
    On cherche pour N=17 au rang n=11
    Pour N=17 un=1 au rang n=12
    On cherche pour N=18 au rang n=0
    On cherche pour N=18 au rang n=1
    On cherche pour N=18 au rang n=2
    On cherche pour N=18 au rang n=3
    On cherche pour N=18 au rang n=4
    On cherche pour N=18 au rang n=5
    On cherche pour N=18 au rang n=6
    On cherche pour N=18 au rang n=7
    On cherche pour N=18 au rang n=8
    On cherche pour N=18 au rang n=9
    On cherche pour N=18 au rang n=10
    On cherche pour N=18 au rang n=11
    On cherche pour N=18 au rang n=12
    On cherche pour N=18 au rang n=13
    On cherche pour N=18 au rang n=14
    On cherche pour N=18 au rang n=15
    On cherche pour N=18 au rang n=16
    On cherche pour N=18 au rang n=17
    On cherche pour N=18 au rang n=18
    On cherche pour N=18 au rang n=19
    Pour N=18 un=1 au rang n=20
    On cherche pour N=19 au rang n=0
    On cherche pour N=19 au rang n=1
    On cherche pour N=19 au rang n=2
    On cherche pour N=19 au rang n=3
    On cherche pour N=19 au rang n=4
    On cherche pour N=19 au rang n=5
    On cherche pour N=19 au rang n=6
    On cherche pour N=19 au rang n=7
    On cherche pour N=19 au rang n=8
    On cherche pour N=19 au rang n=9
    On cherche pour N=19 au rang n=10
    On cherche pour N=19 au rang n=11
    On cherche pour N=19 au rang n=12
    On cherche pour N=19 au rang n=13
    On cherche pour N=19 au rang n=14
    On cherche pour N=19 au rang n=15
    On cherche pour N=19 au rang n=16
    On cherche pour N=19 au rang n=17
    On cherche pour N=19 au rang n=18
    On cherche pour N=19 au rang n=19
    Pour N=19 un=1 au rang n=20
    On cherche pour N=20 au rang n=0
    On cherche pour N=20 au rang n=1
    On cherche pour N=20 au rang n=2
    On cherche pour N=20 au rang n=3
    On cherche pour N=20 au rang n=4
    On cherche pour N=20 au rang n=5
    On cherche pour N=20 au rang n=6
    Pour N=20 un=1 au rang n=7
    On cherche pour N=21 au rang n=0
    On cherche pour N=21 au rang n=1
    On cherche pour N=21 au rang n=2
    On cherche pour N=21 au rang n=3
    On cherche pour N=21 au rang n=4
    On cherche pour N=21 au rang n=5
    On cherche pour N=21 au rang n=6
    Pour N=21 un=1 au rang n=7
    On cherche pour N=22 au rang n=0
    On cherche pour N=22 au rang n=1
    On cherche pour N=22 au rang n=2
    On cherche pour N=22 au rang n=3
    On cherche pour N=22 au rang n=4
    On cherche pour N=22 au rang n=5
    On cherche pour N=22 au rang n=6
    On cherche pour N=22 au rang n=7
    On cherche pour N=22 au rang n=8
    On cherche pour N=22 au rang n=9
    On cherche pour N=22 au rang n=10
    On cherche pour N=22 au rang n=11
    On cherche pour N=22 au rang n=12
    On cherche pour N=22 au rang n=13
    On cherche pour N=22 au rang n=14
    Pour N=22 un=1 au rang n=15
    On cherche pour N=23 au rang n=0
    On cherche pour N=23 au rang n=1
    On cherche pour N=23 au rang n=2
    On cherche pour N=23 au rang n=3
    On cherche pour N=23 au rang n=4
    On cherche pour N=23 au rang n=5
    On cherche pour N=23 au rang n=6
    On cherche pour N=23 au rang n=7
    On cherche pour N=23 au rang n=8
    On cherche pour N=23 au rang n=9
    On cherche pour N=23 au rang n=10
    On cherche pour N=23 au rang n=11
    On cherche pour N=23 au rang n=12
    On cherche pour N=23 au rang n=13
    On cherche pour N=23 au rang n=14
    Pour N=23 un=1 au rang n=15
    On cherche pour N=24 au rang n=0
    On cherche pour N=24 au rang n=1
    On cherche pour N=24 au rang n=2
    On cherche pour N=24 au rang n=3
    On cherche pour N=24 au rang n=4
    On cherche pour N=24 au rang n=5
    On cherche pour N=24 au rang n=6
    On cherche pour N=24 au rang n=7
    On cherche pour N=24 au rang n=8
    On cherche pour N=24 au rang n=9
    Pour N=24 un=1 au rang n=10
    On cherche pour N=25 au rang n=0
    On cherche pour N=25 au rang n=1
    On cherche pour N=25 au rang n=2
    On cherche pour N=25 au rang n=3
    On cherche pour N=25 au rang n=4
    On cherche pour N=25 au rang n=5
    On cherche pour N=25 au rang n=6
    On cherche pour N=25 au rang n=7
    On cherche pour N=25 au rang n=8
    On cherche pour N=25 au rang n=9
    On cherche pour N=25 au rang n=10
    On cherche pour N=25 au rang n=11
    On cherche pour N=25 au rang n=12
    On cherche pour N=25 au rang n=13
    On cherche pour N=25 au rang n=14
    On cherche pour N=25 au rang n=15
    On cherche pour N=25 au rang n=16
    On cherche pour N=25 au rang n=17
    On cherche pour N=25 au rang n=18
    On cherche pour N=25 au rang n=19
    On cherche pour N=25 au rang n=20
    On cherche pour N=25 au rang n=21
    On cherche pour N=25 au rang n=22
    Pour N=25 un=1 au rang n=23
    On cherche pour N=26 au rang n=0
    On cherche pour N=26 au rang n=1
    On cherche pour N=26 au rang n=2
    On cherche pour N=26 au rang n=3
    On cherche pour N=26 au rang n=4
    On cherche pour N=26 au rang n=5
    On cherche pour N=26 au rang n=6
    On cherche pour N=26 au rang n=7
    On cherche pour N=26 au rang n=8
    On cherche pour N=26 au rang n=9
    Pour N=26 un=1 au rang n=10
    On cherche pour N=27 au rang n=0
    On cherche pour N=27 au rang n=1
    On cherche pour N=27 au rang n=2
    On cherche pour N=27 au rang n=3
    On cherche pour N=27 au rang n=4
    On cherche pour N=27 au rang n=5
    On cherche pour N=27 au rang n=6
    On cherche pour N=27 au rang n=7
    On cherche pour N=27 au rang n=8
    On cherche pour N=27 au rang n=9
    On cherche pour N=27 au rang n=10
    On cherche pour N=27 au rang n=11
    On cherche pour N=27 au rang n=12
    On cherche pour N=27 au rang n=13
    On cherche pour N=27 au rang n=14
    On cherche pour N=27 au rang n=15
    On cherche pour N=27 au rang n=16
    On cherche pour N=27 au rang n=17
    On cherche pour N=27 au rang n=18
    On cherche pour N=27 au rang n=19
    On cherche pour N=27 au rang n=20
    On cherche pour N=27 au rang n=21
    On cherche pour N=27 au rang n=22
    On cherche pour N=27 au rang n=23
    On cherche pour N=27 au rang n=24
    On cherche pour N=27 au rang n=25
    On cherche pour N=27 au rang n=26
    On cherche pour N=27 au rang n=27
    On cherche pour N=27 au rang n=28
    On cherche pour N=27 au rang n=29
    On cherche pour N=27 au rang n=30
    On cherche pour N=27 au rang n=31
    On cherche pour N=27 au rang n=32
    On cherche pour N=27 au rang n=33
    On cherche pour N=27 au rang n=34
    On cherche pour N=27 au rang n=35
    On cherche pour N=27 au rang n=36
    On cherche pour N=27 au rang n=37
    On cherche pour N=27 au rang n=38
    On cherche pour N=27 au rang n=39
    On cherche pour N=27 au rang n=40
    On cherche pour N=27 au rang n=41
    On cherche pour N=27 au rang n=42
    On cherche pour N=27 au rang n=43
    On cherche pour N=27 au rang n=44
    On cherche pour N=27 au rang n=45
    On cherche pour N=27 au rang n=46
    On cherche pour N=27 au rang n=47
    On cherche pour N=27 au rang n=48
    On cherche pour N=27 au rang n=49
    On cherche pour N=27 au rang n=50
    On cherche pour N=27 au rang n=51
    On cherche pour N=27 au rang n=52
    On cherche pour N=27 au rang n=53
    On cherche pour N=27 au rang n=54
    On cherche pour N=27 au rang n=55
    On cherche pour N=27 au rang n=56
    On cherche pour N=27 au rang n=57
    On cherche pour N=27 au rang n=58
    On cherche pour N=27 au rang n=59
    On cherche pour N=27 au rang n=60
    On cherche pour N=27 au rang n=61
    On cherche pour N=27 au rang n=62
    On cherche pour N=27 au rang n=63
    On cherche pour N=27 au rang n=64
    On cherche pour N=27 au rang n=65
    On cherche pour N=27 au rang n=66
    On cherche pour N=27 au rang n=67
    On cherche pour N=27 au rang n=68
    On cherche pour N=27 au rang n=69
    On cherche pour N=27 au rang n=70
    On cherche pour N=27 au rang n=71
    On cherche pour N=27 au rang n=72
    On cherche pour N=27 au rang n=73
    On cherche pour N=27 au rang n=74
    On cherche pour N=27 au rang n=75
    On cherche pour N=27 au rang n=76
    On cherche pour N=27 au rang n=77
    On cherche pour N=27 au rang n=78
    On cherche pour N=27 au rang n=79
    On cherche pour N=27 au rang n=80
    On cherche pour N=27 au rang n=81
    On cherche pour N=27 au rang n=82
    On cherche pour N=27 au rang n=83
    On cherche pour N=27 au rang n=84
    On cherche pour N=27 au rang n=85
    On cherche pour N=27 au rang n=86
    On cherche pour N=27 au rang n=87
    On cherche pour N=27 au rang n=88
    On cherche pour N=27 au rang n=89
    On cherche pour N=27 au rang n=90
    On cherche pour N=27 au rang n=91
    On cherche pour N=27 au rang n=92
    On cherche pour N=27 au rang n=93
    On cherche pour N=27 au rang n=94
    On cherche pour N=27 au rang n=95
    On cherche pour N=27 au rang n=96
    On cherche pour N=27 au rang n=97
    On cherche pour N=27 au rang n=98
    On cherche pour N=27 au rang n=99
    On cherche pour N=27 au rang n=100
    On cherche pour N=27 au rang n=101
    On cherche pour N=27 au rang n=102
    On cherche pour N=27 au rang n=103
    On cherche pour N=27 au rang n=104
    On cherche pour N=27 au rang n=105
    On cherche pour N=27 au rang n=106
    On cherche pour N=27 au rang n=107
    On cherche pour N=27 au rang n=108
    On cherche pour N=27 au rang n=109
    On cherche pour N=27 au rang n=110
    Pour N=27 un=1 au rang n=111
    On cherche pour N=28 au rang n=0
    On cherche pour N=28 au rang n=1
    On cherche pour N=28 au rang n=2
    On cherche pour N=28 au rang n=3
    On cherche pour N=28 au rang n=4
    On cherche pour N=28 au rang n=5
    On cherche pour N=28 au rang n=6
    On cherche pour N=28 au rang n=7
    On cherche pour N=28 au rang n=8
    On cherche pour N=28 au rang n=9
    On cherche pour N=28 au rang n=10
    On cherche pour N=28 au rang n=11
    On cherche pour N=28 au rang n=12
    On cherche pour N=28 au rang n=13
    On cherche pour N=28 au rang n=14
    On cherche pour N=28 au rang n=15
    On cherche pour N=28 au rang n=16
    On cherche pour N=28 au rang n=17
    Pour N=28 un=1 au rang n=18
    On cherche pour N=29 au rang n=0
    On cherche pour N=29 au rang n=1
    On cherche pour N=29 au rang n=2
    On cherche pour N=29 au rang n=3
    On cherche pour N=29 au rang n=4
    On cherche pour N=29 au rang n=5
    On cherche pour N=29 au rang n=6
    On cherche pour N=29 au rang n=7
    On cherche pour N=29 au rang n=8
    On cherche pour N=29 au rang n=9
    On cherche pour N=29 au rang n=10
    On cherche pour N=29 au rang n=11
    On cherche pour N=29 au rang n=12
    On cherche pour N=29 au rang n=13
    On cherche pour N=29 au rang n=14
    On cherche pour N=29 au rang n=15
    On cherche pour N=29 au rang n=16
    On cherche pour N=29 au rang n=17
    Pour N=29 un=1 au rang n=18
    On cherche pour N=30 au rang n=0
    On cherche pour N=30 au rang n=1
    On cherche pour N=30 au rang n=2
    On cherche pour N=30 au rang n=3
    On cherche pour N=30 au rang n=4
    On cherche pour N=30 au rang n=5
    On cherche pour N=30 au rang n=6
    On cherche pour N=30 au rang n=7
    On cherche pour N=30 au rang n=8
    On cherche pour N=30 au rang n=9
    On cherche pour N=30 au rang n=10
    On cherche pour N=30 au rang n=11
    On cherche pour N=30 au rang n=12
    On cherche pour N=30 au rang n=13
    On cherche pour N=30 au rang n=14
    On cherche pour N=30 au rang n=15
    On cherche pour N=30 au rang n=16
    On cherche pour N=30 au rang n=17
    Pour N=30 un=1 au rang n=18


A ce stade, suivant le code de votre fonction `syracuse`, tout se passe bien (**1 seul appel récursif par fonction**), ou vous avez dû interrompre le programme car sa **compléxité** est telle qu'il ne peut pas répondre dans un temps raisonnable (**3 appels récursifs par fonction**) !

Écrivez maintenant votre programme de recherche du rang pour lequel $u_n=1$ pour un N donné en utilisant un algorithme itératif. Testez votre code en trouvant les rangs recherchés pour N jusqu'à 100.


```python
def find_syracuse_iter(u0: int) -> int:
    """ Return Syracuse suite value : u0 must be > 0 """
    rang = 0
    un = u0
    while (un != 1):
        rang += 1
        #print(f"On cherche pour N={u0} au rang n={rang}")
        if un % 2 == 0:
            un = un // 2
        else:
            un = 3 * un + 1
    print(f"Pour N={u0} un=1 au rang n={rang}")
    return rang

for i in range(1,101):
    find_syracuse_iter(i)
```

    Pour N=1 un=1 au rang n=0
    Pour N=2 un=1 au rang n=1
    Pour N=3 un=1 au rang n=7
    Pour N=4 un=1 au rang n=2
    Pour N=5 un=1 au rang n=5
    Pour N=6 un=1 au rang n=8
    Pour N=7 un=1 au rang n=16
    Pour N=8 un=1 au rang n=3
    Pour N=9 un=1 au rang n=19
    Pour N=10 un=1 au rang n=6
    Pour N=11 un=1 au rang n=14
    Pour N=12 un=1 au rang n=9
    Pour N=13 un=1 au rang n=9
    Pour N=14 un=1 au rang n=17
    Pour N=15 un=1 au rang n=17
    Pour N=16 un=1 au rang n=4
    Pour N=17 un=1 au rang n=12
    Pour N=18 un=1 au rang n=20
    Pour N=19 un=1 au rang n=20
    Pour N=20 un=1 au rang n=7
    Pour N=21 un=1 au rang n=7
    Pour N=22 un=1 au rang n=15
    Pour N=23 un=1 au rang n=15
    Pour N=24 un=1 au rang n=10
    Pour N=25 un=1 au rang n=23
    Pour N=26 un=1 au rang n=10
    Pour N=27 un=1 au rang n=111
    Pour N=28 un=1 au rang n=18
    Pour N=29 un=1 au rang n=18
    Pour N=30 un=1 au rang n=18
    Pour N=31 un=1 au rang n=106
    Pour N=32 un=1 au rang n=5
    Pour N=33 un=1 au rang n=26
    Pour N=34 un=1 au rang n=13
    Pour N=35 un=1 au rang n=13
    Pour N=36 un=1 au rang n=21
    Pour N=37 un=1 au rang n=21
    Pour N=38 un=1 au rang n=21
    Pour N=39 un=1 au rang n=34
    Pour N=40 un=1 au rang n=8
    Pour N=41 un=1 au rang n=109
    Pour N=42 un=1 au rang n=8
    Pour N=43 un=1 au rang n=29
    Pour N=44 un=1 au rang n=16
    Pour N=45 un=1 au rang n=16
    Pour N=46 un=1 au rang n=16
    Pour N=47 un=1 au rang n=104
    Pour N=48 un=1 au rang n=11
    Pour N=49 un=1 au rang n=24
    Pour N=50 un=1 au rang n=24
    Pour N=51 un=1 au rang n=24
    Pour N=52 un=1 au rang n=11
    Pour N=53 un=1 au rang n=11
    Pour N=54 un=1 au rang n=112
    Pour N=55 un=1 au rang n=112
    Pour N=56 un=1 au rang n=19
    Pour N=57 un=1 au rang n=32
    Pour N=58 un=1 au rang n=19
    Pour N=59 un=1 au rang n=32
    Pour N=60 un=1 au rang n=19
    Pour N=61 un=1 au rang n=19
    Pour N=62 un=1 au rang n=107
    Pour N=63 un=1 au rang n=107
    Pour N=64 un=1 au rang n=6
    Pour N=65 un=1 au rang n=27
    Pour N=66 un=1 au rang n=27
    Pour N=67 un=1 au rang n=27
    Pour N=68 un=1 au rang n=14
    Pour N=69 un=1 au rang n=14
    Pour N=70 un=1 au rang n=14
    Pour N=71 un=1 au rang n=102
    Pour N=72 un=1 au rang n=22
    Pour N=73 un=1 au rang n=115
    Pour N=74 un=1 au rang n=22
    Pour N=75 un=1 au rang n=14
    Pour N=76 un=1 au rang n=22
    Pour N=77 un=1 au rang n=22
    Pour N=78 un=1 au rang n=35
    Pour N=79 un=1 au rang n=35
    Pour N=80 un=1 au rang n=9
    Pour N=81 un=1 au rang n=22
    Pour N=82 un=1 au rang n=110
    Pour N=83 un=1 au rang n=110
    Pour N=84 un=1 au rang n=9
    Pour N=85 un=1 au rang n=9
    Pour N=86 un=1 au rang n=30
    Pour N=87 un=1 au rang n=30
    Pour N=88 un=1 au rang n=17
    Pour N=89 un=1 au rang n=30
    Pour N=90 un=1 au rang n=17
    Pour N=91 un=1 au rang n=92
    Pour N=92 un=1 au rang n=17
    Pour N=93 un=1 au rang n=17
    Pour N=94 un=1 au rang n=105
    Pour N=95 un=1 au rang n=105
    Pour N=96 un=1 au rang n=12
    Pour N=97 un=1 au rang n=118
    Pour N=98 un=1 au rang n=25
    Pour N=99 un=1 au rang n=25
    Pour N=100 un=1 au rang n=25


## Recherche dichotomique récursive !

Écrivez maintenant une fonction de recherche dichotomique dans une liste triée qui répond `True` ou `False` en fonction du résultat de la recherche. Vous pouvez utiliser les **slices** pour accéder à une sous-liste.

La technique qui consiste à résoudre un problème en résolvant plusieurs parties plus petite du problème s'appelle : **diviser pour régner**.


```python
def find_dicho_recur(liste: list, value: int) -> bool:
    """ liste must be sorted
    >>> find_dicho_recur([], 0)
    False
    >>> find_dicho_recur([1], 0)
    False
    >>> find_dicho_recur([1], 1)
    True
    >>> find_dicho_recur([1, 2], 1)
    True
    >>> find_dicho_recur([1, 2], 2)
    True
    >>> find_dicho_recur([1, 2], 3)
    False
    >>> find_dicho_recur([1, 2], -1)
    False
    >>> find_dicho_recur([1,2,3], 0)
    False
    >>> find_dicho_recur([1,2,3], 5)
    False
    >>> find_dicho_recur([1,2,3], 1)
    True
    >>> find_dicho_recur([1,2,3], 2)
    True
    >>> find_dicho_recur([1,2,3], 3)
    True
    >>> find_dicho_recur([1,2,3,4], 1)
    True
    >>> find_dicho_recur([1,2,3,4], 2)
    True
    >>> find_dicho_recur([1,2,3,4], 3)
    True
    >>> find_dicho_recur([1,2,3,4], 4)
    True
    >>> find_dicho_recur([1,2,3,4], -1)
    False
    >>> find_dicho_recur([1,2,3,4], 10)
    False
    """
    #print(f"On travaile sur la liste {liste}")
    result = False
    if liste:
        milieu = len(liste) // 2
        if liste[milieu] == value:
            result = True
        elif value > liste[milieu]:
            result = find_dicho_recur(liste[milieu+1:], value)
        else:
            result = find_dicho_recur(liste[:milieu], value)
    return result
    
def find_dicho_recur2(liste: list, value: int) -> bool:
    """ liste must be sorted
    >>> find_dicho_recur2([], 0)
    False
    >>> find_dicho_recur2([1], 0)
    False
    >>> find_dicho_recur2([1], 1)
    True
    >>> find_dicho_recur2([1, 2], 1)
    True
    >>> find_dicho_recur2([1, 2], 2)
    True
    >>> find_dicho_recur2([1, 2], 3)
    False
    >>> find_dicho_recur2([1, 2], -1)
    False
    >>> find_dicho_recur2([1,2,3], 0)
    False
    >>> find_dicho_recur2([1,2,3], 5)
    False
    >>> find_dicho_recur2([1,2,3], 1)
    True
    >>> find_dicho_recur2([1,2,3], 2)
    True
    >>> find_dicho_recur2([1,2,3], 3)
    True
    >>> find_dicho_recur2([1,2,3,4], 1)
    True
    >>> find_dicho_recur2([1,2,3,4], 2)
    True
    >>> find_dicho_recur2([1,2,3,4], 3)
    True
    >>> find_dicho_recur2([1,2,3,4], 4)
    True
    >>> find_dicho_recur2([1,2,3,4], -1)
    False
    >>> find_dicho_recur2([1,2,3,4], 10)
    False
    """
    #print(f"On travaile sur la liste {liste}")
    result = False
    if liste:
        if len(liste) == 1 :
            result = liste[0] == value
        else:
            milieu = len(liste) // 2
            if value < liste[milieu]:
                result = find_dicho_recur2(liste[:milieu], value)
            else:
                result = find_dicho_recur2(liste[milieu:], value)
    return result

import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)
```




    TestResults(failed=0, attempted=42)



## Rendu de monnaie optimal !

Nous avons programmé le [rendu de monnaie](https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_rendu_de_monnaie) avec un **algorithme glouton** qui est optimal pour les **systèmes de monnaies cannoniques** (comme l'euro).

Mais si nous disposons des pièces : **4, 3 et 1**, pour un rendu de 6, l'algorithme glouton rendra 3 pièces (4+1+1) alors qu'une solution en 2 pièces existe (3+3).

Nous allons utiliser une fonction **récursive** pour trouver la **solution optimale et explorant toutes les possibilités**.

L'idée est de lancer une recherche récursive en choisissant 1 pièce et de garder seulement la solution qui demande le moins de pièces pour la somme restante. Voici un exemple avec [4,3,1] et 8 :
- Je vais utiliser 1 pièce à tour de rôle : 4 puis je lance récursivement ma fonction avec [4,3,1] et 8-4 = 4. Puis je fais pareil avec les pièces 3 puis 1.
- Je sais ainsi que le nombre de pièces total pour chaque possibilité est le résultat de l'appel récursif + 1. Il me suffit donc de choisir la branche qui retourne le moins de pièces.

Et comme le programme est **récursif toutes les possibilités seront automatiquement explorée** pour donner une solution optimale.


```python
def rendu_monnaie(pieces: list, somme: int) -> list:
    """ Return optimal coin's count for money back
        Return None if no solution exists
        pieces : list of int
        >>> rendu_monnaie([], 5) is None
        True
        >>> rendu_monnaie([4,3], 1) is None
        True
        >>> rendu_monnaie([4,3], -1) is None
        True
        >>> rendu_monnaie([4,3], 5) is None
        True
        >>> rendu_monnaie([4,3], 6)
        [3, 3]
        >>> rendu_monnaie([4,3], 8)
        [4, 4]
        >>> rendu_monnaie([4,3,1], 6)
        [3, 3]
        >>> rendu_monnaie([4,3,1], 5)
        [4, 1]        
    """
    #print(f"rendu_monnaie({pieces},{somme})")
    result = None
    if somme == 0: result = []
    else:
        longueur_mini = float('inf')
        for piece in pieces:
            if somme >= piece:
                tmp = rendu_monnaie(pieces, somme - piece)
                if tmp != None :
                    tmp = [piece] + tmp
                    if len(tmp) < longueur_mini:
                        result = tmp
                        longueur_mini = len(tmp)
    return result


def rendu_monnaie2(pieces: list, somme: int) -> list:
    """ Return optimal coin's count for money back
        Return [] if no solution exists
        pieces : list of int    
        >>> rendu_monnaie2([], 5)
        []
        >>> rendu_monnaie2([4,3], 1)
        []
        >>> rendu_monnaie2([4,3], -1)
        []
        >>> rendu_monnaie2([4,3], 5)
        []
        >>> rendu_monnaie2([4,3], 6)
        [3, 3]
        >>> rendu_monnaie2([4,3], 8)
        [4, 4]
        >>> rendu_monnaie2([4,3,1], 6)
        [3, 3]
        >>> rendu_monnaie2([4,3,1], 5)
        [4, 1]
    """
    #print(f"rendu_monnaie2({pieces},{somme})")
    result = []
    longueur_mini = float('inf')
    for piece in pieces:
        if somme == piece:
            result = [piece]
            break
        elif (somme - piece) >= min(pieces):            
            tmp = rendu_monnaie2(pieces, somme - piece)
            if tmp != []:
                tmp = [piece] + tmp
                if len(tmp) < longueur_mini:
                    result = tmp
                    longueur_mini = len(tmp)
    return result

import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)
```




    TestResults(failed=0, attempted=58)



## Rendu de monnaie optimal et dynamique !

La solution ci-dessus qui explore **toutes les possibilités** récursivement est séduisante mais si vous lancez `rendu_monnaie([4,3,1], 25)` avec l'affichage des appels vous allez constater que le nombre d'appels est considérable. Ce qui explique pourquoi `rendu_monnaie([4,3,1], 53)` a du mal à répondre dans un temps raisonnable...

Nous allons donc améliorer notre fonction avec la technique de la **programmation dynamique** en mémorisant les solutions déjà calculées pour les réutiliser au cours du calcul.




```python
def rendu_dyn(pieces: list, somme: int) -> list:
    """ Return optimal coin's count for money back
        Return [] if no solution exists
        pieces : list of POSITIVE int    
        >>> rendu_dyn([], 5)
        []
        >>> rendu_dyn([4,3], 1)
        []
        >>> rendu_dyn([4,3], 0)
        []
        >>> rendu_dyn([4,3], 5)
        []
        >>> rendu_dyn([4,3], 6)
        [3, 3]
        >>> rendu_dyn([4,3], 8)
        [4, 4]
        >>> rendu_dyn([4,3,1], 6)
        [3, 3]
        >>> rendu_dyn([4,3,1], 5)
        [4, 1]
    """
    memoire = [None for _ in range(somme+1)]
    
    def rendu(pieces: list, somme: int) -> list:
        #print(f"rendu({pieces},{somme})")
        if memoire[somme] != None: return memoire[somme]
        result = []
        longueur_mini = float('inf')
        for piece in pieces:
            if somme == piece:
                result = [piece]
                break
            elif (somme - piece) >= min(pieces):            
                tmp = rendu(pieces, somme - piece)
                memoire[somme] = tmp
                if tmp != []:
                    tmp = [piece] + tmp
                    if len(tmp) < longueur_mini:
                        result = tmp
                        longueur_mini = len(tmp)
        memoire[somme] = result
        return result

    return rendu(pieces, somme)

import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS | doctest.NORMALIZE_WHITESPACE, verbose = False)
```




    TestResults(failed=0, attempted=66)



## Rotation d'une image d'un quart de tour en temps constant

Faites l'exercice `Objectif BAC` du livre de NSI page 52. Le corrigé est disponible page 63.

👏👏👏 Bravo ! 👏👏👏
