{"cells":[{"metadata":{"hide_input":true,"hide_output":true,"init_cell":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# Permet de tout executer au lancement du notebook + conserver le notebook actif pendant 2h\nfrom IPython.display import Javascript\nfrom masquer import *\nJavascript(\"\"\"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );\"\"\")","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"<IPython.core.display.Javascript object>","application/javascript":"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );"},"metadata":{}}]},{"metadata":{"hide_input":true,"hide_output":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"from IPython.core.interactiveshell import InteractiveShell\nInteractiveShell.ast_node_interactivity = \"all\"\nHTML(\"\"\"<style>\nh1 {\n  font-family: 'Permanent Marker', cursive;\n  text-align: center;\n  color: red;\n  \n}\nol {\n  list-style-position: inside;\n  margin-left: 1em;\n  list-style-position: outside;\n}\nh2 {\n  font-family: 'Permanent Marker', cursive;\n  color: blue;\n}\nh3 {\n  font-family: 'Permanent Marker', cursive;\n\n}\n</style>\"\"\")","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"<IPython.core.display.HTML object>","text/html":"<style>\nh1 {\n  font-family: 'Permanent Marker', cursive;\n  text-align: center;\n  color: red;\n  \n}\nol {\n  list-style-position: inside;\n  margin-left: 1em;\n  list-style-position: outside;\n}\nh2 {\n  font-family: 'Permanent Marker', cursive;\n  color: blue;\n}\nh3 {\n  font-family: 'Permanent Marker', cursive;\n\n}\n</style>"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"# <span style=\"color:red;\"><center>CHAPITRE 2 - Recursivité</center></span>"},{"metadata":{},"cell_type":"markdown","source":"## III. Limites"},{"metadata":{},"cell_type":"markdown","source":" ### III.1. Limite de la taille de la pile d'appel\n"},{"metadata":{},"cell_type":"markdown","source":" En python par défaut, on ne peut pas réaliser plus de 1000 appels imbriqués sinon on se retrouve avec l'erreur\n```\nRecursionError: maximum recursion depth exceeded in comparison\n```\nSous jupyter, cette limite est portée à 3000 par défaut (ce qui permet en réalité d'aller un tout petit peu en dessous).\n\n\nCe 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.\n\n <img src=\"https://preview.redd.it/0wap3cp4khm01.jpg?auto=webp&s=3dec95610a58f519cdc503061ef41bf85ed63295\" width=\"500\" height=\"500\">\n\nLa solution est d'utiliser la fonction [**setrecursionlimit**](https://docs.python.org/3/library/sys.html#sys.setrecursionlimit) du module **sys**\nDans la documentation python, on peut lire:\n>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.\n\n>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.\n\n\nOn reprend la suite $u_n$ rappelée ci-dessous."},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"def u(n):\n    if n == 0:\n        return 2\n    else:\n        x = u(n-1)\n        return 0.5*(x + 3 / x)","execution_count":4,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Exercice 1.\n1. Calculez u(10000)\n2. 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."},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 1.\n","execution_count":5,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 2.\n","execution_count":6,"outputs":[]},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### III.2. Limite de complexité"},{"metadata":{},"cell_type":"markdown","source":"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.\n\n\nSi 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:"},{"metadata":{"pixiedust":{"displayParams":{}},"trusted":true},"cell_type":"code","source":"def u(n):\n    if n == 0:\n        return 2\n    else:\n        return 0.5*(u(n-1) + 3 / u(n-1))\n\nfrom time import time\nfor i in range(25):\n    t = time()\n    racinedetrois = u(i)\n    print(i,time()-t)","execution_count":7,"outputs":[{"output_type":"stream","text":"0 2.3126602172851562e-05\n1 6.4373016357421875e-06\n2 5.0067901611328125e-06\n3 6.198883056640625e-06\n4 9.775161743164062e-06\n5 1.9073486328125e-05\n6 3.695487976074219e-05\n7 7.200241088867188e-05\n8 0.00014519691467285156\n9 0.0002932548522949219\n10 0.0005791187286376953\n11 0.0012617111206054688\n12 0.0022325515747070312\n13 0.0034668445587158203\n14 0.006333827972412109\n15 0.008409261703491211\n16 0.029224634170532227\n17 0.03555464744567871\n18 0.08672499656677246\n19 0.12528204917907715\n20 0.2587292194366455\n21 0.5444915294647217\n22 0.9242415428161621\n23 1.5842571258544922\n24 3.4333577156066895\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"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."},{"metadata":{},"cell_type":"markdown","source":"### Exercice 2. \nLa suite de fibonaci est définie par:\n\n$F_0 = 1$\n\n$F_1 = 1$\n\n$F_n = F_{n-1} + F_{n-2}$ $\\forall n \\in \\mathbb{N}, n > 1$\n1. Programmez une foncton qui prend comme argument un entier **n** et qui renvoie la valeur de $F_n$.\n2. Quelle est l'ordre de grandeur de la valeur de n la plus grande accessible avec cette fonction ?\n3. Programmez cette fonction de manière iterative.\n4. Quelle est l'ordre de grandeur de la valeur de n la plus grande accessible avec cette fonction ?\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":""},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":""},{"metadata":{},"cell_type":"markdown","source":"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."},{"metadata":{"trusted":true},"cell_type":"code","source":"import sys\nsys.setrecursionlimit(10000)\n\nmemoire = [1,1]\ndef F(n):\n    global memoire\n    if n < len(memoire):\n        return memoire[n]\n    else:\n        memoire.append(F(n-1) + F(n-2))\n        return memoire[n]\n\nt = time()\nF(5000)\nprint(time()-t)","execution_count":8,"outputs":[{"output_type":"execute_result","execution_count":8,"data":{"text/plain":"6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626"},"metadata":{}},{"output_type":"stream","text":"0.00910186767578125\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"Et l'on peut reprendre les calculs là ou on s'était arrêté car tout est resté en mémoire"},{"metadata":{"trusted":true},"cell_type":"code","source":"t = time()\nF(5000)\nprint(time()-t)","execution_count":9,"outputs":[{"output_type":"execute_result","execution_count":9,"data":{"text/plain":"6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626"},"metadata":{}},{"output_type":"stream","text":"0.002252817153930664\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"<a href=\"TD_02_2.ipynb\">TD_02_2</a>\n    \n<center> <a href=\"cours_02_2.ipynb\"><= PRECEDENT</a></center>"}],"metadata":{"celltoolbar":"none","kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.7.8","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"varInspector":{"cols":{"lenName":16,"lenType":16,"lenVar":40},"kernels_config":{"python":{"delete_cmd_postfix":"","delete_cmd_prefix":"del ","library":"var_list.py","varRefreshCmd":"print(var_dic_list())"},"r":{"delete_cmd_postfix":") ","delete_cmd_prefix":"rm(","library":"var_list.r","varRefreshCmd":"cat(var_dic_list()) "}},"types_to_exclude":["module","function","builtin_function_or_method","instance","_Feature"],"window_display":false}},"nbformat":4,"nbformat_minor":4}