#!/usr/bin/env python
# coding: utf-8

# # Programmation dynamique
# 
# Illustration avec la suite de Fibonacci définie par :
# 
# - $F_0 = 0$
# - $F_1 = 1$
# - $\forall n \in \mathbb{N}, F_{n+2} = F_{n+1}+F_n$
# 

# ## Approche récursive
# 
# > **Simple**

# In[ ]:


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


# In[ ]:


fibo(3)


# In[ ]:


from metakernel import register_ipython_magics
register_ipython_magics()


# In[ ]:


get_ipython().run_cell_magic('tutor', '', '\ndef fibo(n):\n    if n == 0 :\n        return 0   \n    elif n == 1 :\n        return 1\n    else :\n        return fibo(n-1) + fibo(n-2)\n\nfibo(3)\n')


# > Mais **inefficace**
# >
# > Le temps de calcul est de plusieurs dizaines de secondes, sur une machine récente.

# In[ ]:


import time

def fibo(n):
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)
            
t0 = time.time()
fibo(40)
print(time.time() - t0)


# En cause : la multitude des appels récursifs nous conduit à refaire des calculs déjà effectués.
# 
# ![image](https://glassus.github.io/terminale_nsi/T3_Algorithmique/3.2_Programmation_dynamique/data/arbre.png)
# 
# Le calcul de ```fibo(2)``` se retrouve ainsi 5 fois dans l'arbre.
# 
# > Pour résoudre notre problème, on le divise en problèmes plus petits, mais contrairement aux algorithmes de dichotomie, ou du tri-fusion, ici les problèmes ne sont pas indépendants. Une approche par diviser pour régner est donc impossible.
# >
# >Les problèmes se **recouvrent**, ce qui nous amène à refaire des choses déjà faites. 
# 
# 

# ## La mémoïsation
# 
# Pour éviter de recalculer (par exemple) 5 fois ```fibo(2)``` on peut stocker le résultat de chaque calcul, par exemple dans un dictionnaire. Ainsi, à chaque demande de calcul :
# 
# - Soit le calcul a déjà été effectué : on a donc juste à le lire dans le dictionnaire.
# - Soit le calcul n'a jamais été effectué : on l'effectue, et **on stocke le résultat dans le dictionnaire**.

# In[ ]:


get_ipython().run_cell_magic('tutor', '', '\ndict_fibo = {0:0, 1:1}\ndef fibo(n):\n    if n in dict_fibo:\n        return dict_fibo[n]\n    dict_fibo[n] = fibo(n-1) + fibo(n-2)\n    return dict_fibo[n]\n\nfibo(3)\n')


# In[ ]:


import time
          
t0 = time.time()
fibo(40)
print(time.time() - t0)


# In[ ]:


dict_fibo


# ### Remarques
# 
# > Le dictionnaire (global) ```dict_fibo``` doit être **à l'extérieur** de la fonction, sinon il est réinitialisé à chaque appel récursif !
# >
# > Un dictionnaire (global) étant un type mutable, sa modification à l'intérieur de la fonction ne pose pas de problème. Toutefois, ce genre de pratique est déconseillé : si par exemple on appelle 2 fois la fonction ```fibo```, le dictionnaire n'est pas réinitialisé entre-temps (ce qui dans notre cas n'est pas problématique, mais cela pourrait l'être).
# >
# > Pour éviter cela on peut utiliser une fonction **englobante** (appelée ici ```fibonacci``` ) :

# In[ ]:


def fibonacci(n):
    dict_fibo = {0:0, 1:1}
    def fibo(n):
        if n in dict_fibo:
            return dict_fibo[n]
        dict_fibo[n] = fibo(n-1) + fibo(n-2)
        return dict_fibo[n]
    return fibo(n)


# In[ ]:


fibonacci(50)


# > Observez la définition d'une fonction **à l'intérieur** d'une autre. Cela ne pose aucun problème, mais attention, cette fonction n'existe pas à l'extérieur de sa fonction englobante.

# #### **Mémoïsation automatique en Python**
# 
# La fonction ```lru_cache``` du module ```functools``` permet de mémoïser automatiquement une fonction récursive. Il suffit, juste avant d'écrire la fonction, de mettre la ligne ```@lru_cache``` (appelée *décorateur*).

# In[ ]:


import time
from functools import lru_cache

@lru_cache  #(1)
def fibo(n): #(2)
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)
    
t0 = time.time()
fibo(35)
print(time.time() - t0)


# ## Méthode *top-down* vs *bottom-up*
# 
# La structure récursive naturelle de la suite de Fibonacci nous a conduit vers un programme qui calcule (ou plutôt appelle) les valeurs **de haut en bas**.
# 
# Et si on commençait par le bas ?
# 
# Si nous devions calculer mentalement le 6ème terme de la suite de Fibonacci, on commencerait par calculer le 3ème, puis le 4ème, puis le 5ème et enfin le 6ème.
# 

# In[ ]:


def fibo(n):
    dict_fibo = {}
    dict_fibo[0] = 0
    dict_fibo[1] = 1
    for k in range(2, n+1):
        dict_fibo[k] = dict_fibo[k-1] + dict_fibo[k-2]
    return dict_fibo[n]


# Cette méthode itérative part du **bas pour aller vers le haut**. On parle de méthode *bottom-up*. 
# De manière plus générale, cette méthode est basée sur le fait de résoudre des problèmes de petite taille, puis de plus en plus gros, jusqu'au problème final.

# ## Bilan des méthodes
# 
# - Lors d'un calcul effectué de manière récursive, il peut arriver que de multiples appels récursifs soient identiques. Pour éviter de recalculer plusieurs fois la même chose, on peut stocker les résultats intermédiaires. On appelle cette technique la **mémoïsation**.  
# Cette technique minimise le nombre d'opérations et accélère grandement l'exécution du programme. Le prix à payer est l'utilisation d'une structure de stockage des valeurs intermédiaires, et donc une augmentation de la mémoire utilisée par le programme.
# 
# - Lors d'un calcul effectué de manière itérative, il est parfois plus simple de commencer par une «petite» version du problème pour progressivement remonter vers la solution du problème global.

#