In [2]:
# Permet de tout executer au lancement du notebook + conserver le notebook actif pendant 2h
from IPython.display import Javascript
from masquer import *
Javascript("""
function repeter(){
IPython.notebook.kernel.execute("a=1");
}
// execute a = 1 en python toutes les 8 minutes pendant 2h
let timerId = setInterval(() => repeter(), 4800);
setTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);

// Supprimer la taille limite pour la sortie d'une cellule
IPython.OutputArea.prototype._should_scroll = function(lines) {
    return false;
};
IPython.notebook.kernel.execute("url = '" + window.location + "'");

// Exécuter toutes les cellule du notebook
    require(
        ['base/js/namespace', 'jquery'], 
        function(jupyter, $) {
            
                
                jupyter.actions.call('jupyter-notebook:run-all-cells-below');
                jupyter.actions.call('jupyter-notebook:save-notebook');
                Jupyter.actions.call('jupyter-notebook:hide-header')

        }
    );""")
Out[2]:
In [3]:
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
HTML("""<style>
h1 {
  font-family: 'Permanent Marker', cursive;
  text-align: center;
  color: red;
  
}
ol {
  list-style-position: inside;
  margin-left: 1em;
  list-style-position: outside;
}
h2 {
  font-family: 'Permanent Marker', cursive;
  color: blue;
}
h3 {
  font-family: 'Permanent Marker', cursive;

}
</style>""")
Out[3]:

CHAPITRE 2 - Recursivité

III. Limites

III.1. Limite de la taille de la pile d'appel

En python par défaut, on ne peut pas réaliser plus de 1000 appels imbriqués sinon on se retrouve avec l'erreur

RecursionError: maximum recursion depth exceeded in comparison

Sous jupyter, cette limite est portée à 3000 par défaut (ce qui permet en réalité d'aller un tout petit peu en dessous).

Ce système est là pour éviter les problèmes de boucle infinie qui peuvent se poser très facilement quand on écrit une fonction récursive et que l'on oublie la condition d'arrêt.

La solution est d'utiliser la fonction setrecursionlimit du module sys Dans la documentation python, on peut lire:

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

On reprend la suite $u_n$ rappelée ci-dessous.

In [4]:
def u(n):
    if n == 0:
        return 2
    else:
        x = u(n-1)
        return 0.5*(x + 3 / x)

Exercice 1.

  1. Calculez u(10000)
  2. Proposez un fonction u3 sur le modèle de u(n) qui prend pour argument un entier a et un float epsilon (plus ce qui vous sera nécessaire) et qui renvoie $u_n \approx \sqrt{a}$ lorsque $|u_n - u_{n-1}| < epsilon$. Votre fonction devra aussi renvoyer le nombre d'appels imbriqués réalisés.
In [5]:
# Question 1.
In [6]:
# Question 2.

III.2. Limite de complexité

La fonction u(n) précédente appelle une seule fois la fonction u(n-1) et ainsi de suite. Le résultat est un appel pour chaque n, avec chaque appel réalisé en temps constant d'où une complexité en O(n) (en gros un temps d'exécution proportionnel à n sur une même machine) comme dans le cas de l'utilisation d'un boucle for pour le calcul.

Si on utilise la fonction u(n) ci-dessous, u(n) appelle deux fois u(n-1) qui appellent chacune deux fois u(n-2) etc... On se retrouve avec $2^n$ appels et donc un temps d'exécution exponentiel! (le temps est proportionnel à $2^n$ et double donc lorsque n augmente de 1. Faison l'expérience:

In [7]:
def u(n):
    if n == 0:
        return 2
    else:
        return 0.5*(u(n-1) + 3 / u(n-1))

from time import time
for i in range(25):
    t = time()
    racinedetrois = u(i)
    print(i,time()-t)
0 2.3126602172851562e-05
1 6.4373016357421875e-06
2 5.0067901611328125e-06
3 6.198883056640625e-06
4 9.775161743164062e-06
5 1.9073486328125e-05
6 3.695487976074219e-05
7 7.200241088867188e-05
8 0.00014519691467285156
9 0.0002932548522949219
10 0.0005791187286376953
11 0.0012617111206054688
12 0.0022325515747070312
13 0.0034668445587158203
14 0.006333827972412109
15 0.008409261703491211
16 0.029224634170532227
17 0.03555464744567871
18 0.08672499656677246
19 0.12528204917907715
20 0.2587292194366455
21 0.5444915294647217
22 0.9242415428161621
23 1.5842571258544922
24 3.4333577156066895

De manière générale, une fonction récursive qui s'appelle plus d'une fois donnera une complexité exponentielle, il faudra donc bien y faire attention lors du codage d'un fonction récursive.

Exercice 2.

La suite de fibonaci est définie par:

$F_0 = 1$

$F_1 = 1$

$F_n = F_{n-1} + F_{n-2}$ $\forall n \in \mathbb{N}, n > 1$

  1. Programmez une foncton qui prend comme argument un entier n et qui renvoie la valeur de $F_n$.
  2. Quelle est l'ordre de grandeur de la valeur de n la plus grande accessible avec cette fonction ?
  3. Programmez cette fonction de manière iterative.
  4. Quelle est l'ordre de grandeur de la valeur de n la plus grande accessible avec cette fonction ?
In [ ]:
 
In [ ]:
 

Il est possible de remédier à ce problème de complexité de la fonction récursive en utilisant la mise en cache ou mémoïsation. Il s'agit de stocker dans un tableau la valeur de chaque terme déjà calculé afin d'y accéder rapidement sans le recalculer. Le tableau doit être accessible à tous les niveaux de la pile d'appel.

In [8]:
import sys
sys.setrecursionlimit(10000)

memoire = [1,1]
def F(n):
    global memoire
    if n < len(memoire):
        return memoire[n]
    else:
        memoire.append(F(n-1) + F(n-2))
        return memoire[n]

t = time()
F(5000)
print(time()-t)
Out[8]:
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
0.00910186767578125

Et l'on peut reprendre les calculs là ou on s'était arrêté car tout est resté en mémoire

In [9]:
t = time()
F(5000)
print(time()-t)
Out[9]:
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
0.002252817153930664