{"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":"## I. Définition"},{"metadata":{},"cell_type":"markdown","source":"**def:**\nUne fonction récursive est une fonction qui s'appelle elle-même. C'est la version informatique de la récurrence mathématique.\n<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/methodshop/5245100040\" title=\"Inception in Real-Time [video]\"><img src=\"https://live.staticflickr.com/5283/5245100040_fc92c29d74_c.jpg\" width=\"643\" height=\"730\" alt=\"Inception in Real-Time [video]\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n\n\n**Exemple:**\nSi on définit une suite $u_n$ telle que\n* $u_0 = 2$\n* $u_n = \\frac{1}{2}\\left(u_{n-1} + \\frac{3}{u_{n-1}}\\right)$ $\\forall n \\in \\mathbb{N}^{*}$\n\nOn peut la programmer comme 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        return 0.5*(u(n-1) + 3 / u(n-1))\n    \nu(0)\nu(1)\nu(2)","execution_count":4,"outputs":[{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"2"},"metadata":{}},{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"1.75"},"metadata":{}},{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"1.7321428571428572"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Ainsi $u_0$ renvoie directement 2, c'est la **condition d'arrêt**. Si n est supérieur à 0, la fonction s'appelle elle même avec un argument inférieur, qui s'appelle elle même avec un argument inférieur, etc.. jusqu'à atteindre la condition d'arrêt. **Il ne faudra jamais oublier cette condition d'arrêt sans quoi le programme ne s'arrêterait plus**.\n<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/136049057@N03/23400119630/in/photolist-C6Vb6T-BDMJjs-8GW6WZ-8uqz8S-2bpHbGE-qo5nVF-ai3WGX-aTofHg-nrGRY5-bgqBY6-kLi85B-8DNb6H-2dVqzNv-piYzbW-JW3nbi-edU54o-8yod8u-912JP5\" title=\"Am i dreaming ?\"><img src=\"https://live.staticflickr.com/731/23400119630_8106621a17_c.jpg\" width=\"800\" height=\"450\" alt=\"Am i dreaming ?\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>"},{"metadata":{},"cell_type":"markdown","source":"### Exercice 1\n1. Que se passerait-il si on appelait u(-1) ?\n2. Corriger la fonction à l'aide d'un **assert** afin de vérifier que n est bien dans l'ensemble de définition de la fonction\n3. Que se passerait-il si on appelait u(1.5) ?\n4. Corriger la fonction à l'aide d'un deuxième **assert** afin de vérifier que n est bien un int."},{"metadata":{},"cell_type":"markdown","source":"1. ***Répondre ici***"},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# 2.\n","execution_count":5,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"3. ***Répondre ici***"},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# 4.\n","execution_count":6,"outputs":[]},{"metadata":{"hide_input":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"cacher_code(\"Solution de la 4.\")","execution_count":7,"outputs":[{"output_type":"execute_result","execution_count":7,"data":{"text/plain":"<IPython.core.display.HTML object>","text/html":"\n    <script>\n        function code_toggle_12855399067706410892() {\n            $('div.cell.code_cell.rendered.selected').next().find('div.input').toggle();\n        }\n\n        $('div.cell.code_cell.rendered.selected').find(\"div.input\").hide();\n    </script>\n\n    <a href=\"javascript:code_toggle_12855399067706410892()\">Solution de la 4. </a>\n    "},"metadata":{}}]},{"metadata":{"hide_input":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"def u(n):\n    r\"\"\"\n    Renvoie la valeur de la suite $u_n$ définie par\n     u_0 = 2\n     u_n = 0.5 * (u_(n-1) + 3 / u_(n-1)) pour tout entier positif\n    \"\"\"\n    assert n >= 0, \"n doit être positif ou nul\"\n    assert type(n)==int, \"n doit être un entier\"\n    \n    if n == 0:\n        return 2\n    else:\n        return 0.5*(u(n-1) + 3 / u(n-1))","execution_count":8,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"On peut souvent programmer une même chose en utilisant une fonction itérative (avec une boucle) ou une fonction récursive.\n\nNous allons l'expérimenter avec la fonction factorielle qui s'y prête bien. C'est une fonction définie sur les entiers naturels telle que:\n$$n! = \\prod_{k = 1}^{n} k = n\\times \\prod_{k = 1}^{n-1}k = n \\times (n - 1)!$$\n\nOn peut donc calculer $n!$ en faisant une boucle. Une variable est initialisée à 1 puis est multipliée par un entier plus grand à chaque tout de boucle. On utilise en fait la définition $n! = \\prod_{k = 1}^{n} k$. \n\nOn peut aussi calculer $n!$ en utilisant la définition $n! = n \\times (n - 1)!$ et la condition d'arrêt $1! = 1$."},{"metadata":{},"cell_type":"markdown","source":"### Exercice 2\n1. Proposer une implémentation de la fonction factorielle en itératif\n2. Même question en récursif.\n3. Calculer $6!$ avec vos deux fonctions et comparer le résultat"},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 1\n","execution_count":9,"outputs":[]},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 2\n","execution_count":10,"outputs":[]},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 3\n","execution_count":11,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Lorsque la définition de la fonction est récursive, il sera très facile de la programmer de cette manière. Idem lorsque la définition est itérative.\nMais cela n'est pas une obligation."},{"metadata":{},"cell_type":"markdown","source":"### Exercice 3\n1. Proposer une implémentation itérative de la suite **u**"},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 1\n","execution_count":12,"outputs":[]},{"metadata":{"hide_input":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"cacher_code(\"solution\",output=True)","execution_count":13,"outputs":[{"output_type":"execute_result","execution_count":13,"data":{"text/plain":"<IPython.core.display.HTML object>","text/html":"\n    <script>\n        function code_toggle_2220602350609989405() {\n            $('div.cell.code_cell.rendered.selected').next().find('div.input').toggle();\n            $('div.cell.code_cell.rendered.selected').next().find('div.output').toggle();\n        }\n\n        $('div.cell.code_cell.rendered.selected').find(\"div.input\").hide();\n    </script>\n\n    <a href=\"javascript:code_toggle_2220602350609989405()\">solution </a>\n    "},"metadata":{}}]},{"metadata":{"hide_input":true,"hide_output":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"def u_iter(n):\n    rep = 2\n    for i in range(1,n+1):\n        rep = 0.5*(rep + 3 / rep)\n    return rep\n\n# Comparaison des valeurs obtenues en iteratif et en récursif\nu(0), u_iter(0)\nu(1), u_iter(1)\nu(2), u_iter(2)","execution_count":14,"outputs":[{"output_type":"execute_result","execution_count":14,"data":{"text/plain":"(2, 2)"},"metadata":{}},{"output_type":"execute_result","execution_count":14,"data":{"text/plain":"(1.75, 1.75)"},"metadata":{}},{"output_type":"execute_result","execution_count":14,"data":{"text/plain":"(1.7321428571428572, 1.7321428571428572)"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"### Exercice 4\n1. Proposer une fonction **puissance_iter** prenant comme argument un float **x** et n entier **n** et qui renvoie $x^n$ calculé de manière itérative.\n2. Proposer une fonction **puissance_rec** prenant comme argument un float **x** et n entier **n** et qui renvoie $x^n$ calculé de manière récursive."},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 1\n","execution_count":15,"outputs":[]},{"metadata":{"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# question 2\n","execution_count":16,"outputs":[]},{"metadata":{"hide_input":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"cacher_code(\"Coup de pouce\",for_markdown=True)","execution_count":17,"outputs":[{"output_type":"execute_result","execution_count":17,"data":{"text/plain":"<IPython.core.display.HTML object>","text/html":"\n    <script>\n        function code_toggle_8862889895674458949() {\n            $('div.cell.code_cell.rendered.selected').next().find('div.inner_cell').toggle();\n        }\n\n        $('div.cell.code_cell.rendered.selected').find(\"div.input\").hide();\n    </script>\n\n    <a href=\"javascript:code_toggle_8862889895674458949()\">Coup de pouce </a>\n    "},"metadata":{}}]},{"metadata":{"hide_input":true},"cell_type":"markdown","source":"Pour la version itérative, il faut utiliser $x^n = \\prod_{k=1}^{n} x$\n\n\nPour la version recursive, on utilise $x^n = x \\times x^{n-1}$ avec $x^0 = 1$"},{"metadata":{},"cell_type":"markdown","source":"<center> <a href=\"cours_02_2.ipynb\">SUIVANT =></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}