{"id":4693,"date":"2012-06-21T17:45:12","date_gmt":"2012-06-21T21:45:12","guid":{"rendered":"http:\/\/cscircles.cemc.uwaterloo.ca\/?page_id=4693"},"modified":"2018-02-05T02:45:17","modified_gmt":"2018-02-05T07:45:17","slug":"16-fr","status":"publish","type":"page","link":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/16-fr\/","title":{"rendered":"16: R\u00e9cursivit\u00e9"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nMain French translator: Brice Canvel, brice.canvel@gmail.com<br \/>\nOriginal lesson author: Graeme Kemkes, gdkemkes@alumni.uwaterloo.ca<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/<br \/>\nFor the full site, visit http:\/\/cscircles.ca-->\n<p>Nous avons vu que les fonctions nous permettent d'organiser et de r\u00e9utiliser des parties de notre code. Nous avons vu \u00e9galement que les fonctions peuvent \u00eatre d\u00e9finies \u00e0 partir d'autres fonctions. Dans cette le\u00e7on, nous allons apprendre qu'une fonction peut \u00eatre d\u00e9finie \u00e0 partir d'elle-m\u00eame! Cette approche tr\u00e8s utile s'appelle la <em>r\u00e9cursion<\/em>. La l\u00e9gende dit que \"pour comprendre la r\u00e9cursion, il faut d'abord comprendre la r\u00e9cursion.\"<\/p>\n<h1>Exemple<\/h1>\n<p>Dans notre le\u00e7on sur les boucles, nous avons utilis\u00e9 une boucle\u00a0<code>while<\/code>\u00a0pour g\u00e9n\u00e9rer la sortie suivante.<\/p>\n<pre>5\r\n4\r\n3\r\n2\r\n1\r\nDecollage!<\/pre>Voici un programme qui utilise la r\u00e9cursion pour arriver au m\u00eame r\u00e9sultat.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform0\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox0'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Un compte \u00e0 rebours utilisant la r\u00e9cursion<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 214px;'><textarea wrap='off' name='usercode0' id='usercode0'  cols=10 rows=8 readonly='readonly'  style = 'height : 214px;'  class='pyboxCode RO'>\ndef compter(n):\n  if n == 0:\n    print('Decollage!')\n  else:\n    print(n)\n    compter(n - 1) # appel recursive\n\ncompter(5) # premier appel<\/textarea><\/div>\n<div id='pbhistory0' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit0' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(0)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(0,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"cca3a2bdae1017a34ec4694da7236a1b\"\/>\n<div id='pbresults0' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit0\").value = \"Run program\";document.getElementById(\"inputInUse0\").value = \"N\";<\/script>\n<\/p>\n<p>Ajoutons-nous quelques instructions print pour nous aider \u00e0 comprendre ce qui se passe. Cette version du programme lit l'entr\u00e9e pour d\u00e9terminer le nombre initial.<br \/>\n<form class=\"pbform\" action=\"#\" id=\"pbform1\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox1'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Un compte \u00e0 rebours utilisant la r\u00e9cursion<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 292px;'><textarea wrap='off' name='usercode1' id='usercode1'  cols=10 rows=11 readonly='readonly'  style = 'height : 292px;'  class='pyboxCode RO'>\ndef compter(n):\n  print('D\u00e9but de compter(',n,')')\n  if n == 0:\n    print('Decollage!')\n  else:\n    print(n)\n    compter(n - 1)\n  print('Fin de compter(',n,')')\n\nlimit = int(input())\ncompter(limit)<\/textarea><\/div>\n<div id='pbhistory1' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput1\">You may enter input for the program in the box below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit1' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch1\" value=\"Input Switch\" onclick=\"pbInputSwitch(1,'N')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(1)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(1,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"369bfa8c86bc3fff5eb6abcf085eff33\"\/>\n<div id='pbresults1' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(1,\"N\");<\/script>\n<\/p>\n<p>Vous pouvez utiliser <strong>Tape entr\u00e9e<\/strong>\u00a0avec le programme ci-dessus afin d'essayer d'autres valeurs d'entr\u00e9es. Essayez d'abord avec 0 puis 1.<\/p>\n<p>Quand l'entr\u00e9e est 5, le programme appelle tout d'abord une copie de la fonction\u00a0<code>compter<\/code>\u00a0avec\u00a0<code>n=5<\/code>, ce qui affiche\u00a0<code>5<\/code>\u00a0et appelle <code>compter(4)<\/code>.\u00a0Cela continue jusqu'\u00e0\u00a0<code>compter(0)<\/code>, qui naffiche\u00a0<code>\"Decollage!\"<\/code>\u00a0et n'appelle plus\u00a0<code>compter<\/code>. Quand Python termine d'ex\u00e9cuter l'appel pour\u00a0<code>n=0<\/code>\u00a0de la fonction\u00a0<code>compter<\/code>, Python retourne \u00e0 la fonction qui l'a appel\u00e9e, qui n'est autre que l'appel \u00e0 la fonction <code>compter<\/code>\u00a0pour\u00a0<code>n=1.<\/code>On retourne ensuite \u00e0 l'appel pour\u00a0<code>n=2<\/code>, etc.<\/p>\n<p>Maintenant c'est \u00e0 vous d'\u00e9crire du code. Modifiez la fonction\u00a0<code>compter<\/code>\u00a0pour qu'elle compte en augmentant plut\u00f4t qu'en diminuant.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform2\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox2'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>D\u00e9collage invers\u00e9<\/span><\/div>Ecrivez une fonction r\u00e9cursive\u00a0<code>decompter(n)<\/code>\u00a0qui affiche 'Decollage!' suivi des nombres <code>1<\/code>\u00a0\u00e0\u00a0<code>n<\/code>\u00a0sur des lignes s\u00e9par\u00e9es. <a class=\"hintlink\"  id=\"hintlink3\">Indice<\/a><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode2' id='usercode2'  cols=10 rows=20   class='pyboxCode RW'>\ndef compter(n):\n  if n == 0:\n    print('Decollage!')\n  else:\n    print(n)\n    compter(n - 1)\n<\/textarea><\/div>\n<div id='pbhistory2' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput2\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode2' value='def compter(n):\\n  if n == 0:\\n    print(\\u0027Decollage!\\u0027)\\n  else:\\n    print(n)\\n    compter(n - 1)\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit2' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch2\" value=\"Input Switch\" onclick=\"pbInputSwitch(2,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(2)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(2,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect2' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(2,'16.countup')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(2,descape($('#defaultCode2').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(2);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"0330e86685ad3042742f3eff76d491a2\"\/>\n<div id='pbresults2' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(2);});pbInputSwitch(2,\"Y\");<\/script>\n<\/p>\n<p>Maintenant modifions-nous notre programme\u00a0<code>compter<\/code>\u00a0pour qu'il d\u00e9cr\u00e9mente par 2: p. ex. quand on commence \u00e0 5 la sortie sera 5, 3, 1, Decollage! Nous devons changer l'argument de la fonction de\u00a0<code>n-1<\/code>\u00a0en\u00a0<code>n-2<\/code>. Y a-t-il autre chose \u00e0 changer?<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform4\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox4'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Tentative de compte \u00e0 rebours par incr\u00e9ments de 2<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 214px;'><textarea wrap='off' name='usercode4' id='usercode4'  cols=10 rows=8 readonly='readonly'  style = 'height : 214px;'  class='pyboxCode RO'>\ndef compterParDeux(n):\n  if n == 0:\n    print('Decollage!')\n  else:\n    print(n)\n    compterParDeux(n - 2)\n\ncompterParDeux(5)<\/textarea><\/div>\n<div id='pbhistory4' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit4' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(4)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(4,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"3b2fac8aaa0f0fc7478c812d91e0a8c2\"\/>\n<div id='pbresults4' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit4\").value = \"Run program\";document.getElementById(\"inputInUse4\").value = \"N\";<\/script>\n<\/p>\n<p>Vous pouvez voir que ce programme ne fait pas ce que nous souhaitons. Il affiche <code>5, 3, 1<\/code>, comme nous le voulions mais au lieu de s'arr\u00eater, il continue avec\u00a0<code>-1, -3, -5<\/code>\u00a0et s'ex\u00e9cute sans fin. (Plus exactement, il tombe \u00e0 cours de temps et de m\u00e9moire car chaque appel r\u00e9cursive utilise un peu plus de m\u00e9moire de travail.)<\/p>\n<p>Lorsque l'on cr\u00e9e une fonction r\u00e9cursive, il faut ensurer que la s\u00e9quence des appels ne continue pas ind\u00e9finiment! Modifiez le programme <code>compterParDeux<\/code> pour qu'il s'arr\u00eate correctement \u00e0 1 (ou 2 si n est pair) et affiche 'Decollage!'.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform5\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox5'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Double Time<\/span><\/div>Modifiez ce programme pour qu'il compte \u00e0 rebours avec un incr\u00e9ment de 2.<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode5' id='usercode5'  cols=10 rows=20   class='pyboxCode RW'>\ndef compterParDeux(n):\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    compterParDeux(n - 2)\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory5' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput5\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode5' value='def compterParDeux(n):\\n  if n == 0:\\n    print(\\u0027Blastoff!\\u0027)\\n  else:\\n    print(n)\\n    compterParDeux(n - 2)\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit5' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch5\" value=\"Input Switch\" onclick=\"pbInputSwitch(5,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(5)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(5,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect5' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(5,'16.countdownby2')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(5,descape($('#defaultCode5').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(5);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse5\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"5\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"08d9ed62e42522145e92c1ab361fa561\"\/>\n<div id='pbresults5' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(5);});pbInputSwitch(5,\"Y\");<\/script>\n<\/p>\n<h1>D\u00e9finir des Fonctions R\u00e9cursives<\/h1>\n<p>Une<em> fonction r\u00e9cursive<\/em> signifie tout simplement une fonction qui s'appelle elle-m\u00eame. Mais il doit y avoir des conditions dans lesquelles la fonction ne s'appelle pas elle-m\u00eame sinon le programme s'ex\u00e9cute pour toujours (nous l'avons vu\u00a0pr\u00e9c\u00e9demment). La <strong>condition d'arr\u00eat<\/strong> est la partie de la fonction r\u00e9cursive qui fait qu'elle ne va plus s'appeler elle-m\u00eame. Dans l'exemple ci-dessus, c'\u00e9tait\u00a0<code>n&lt;=0<\/code>. D\u00e9finir une fonction r\u00e9cursive demande de bien choisir cette condition d'arr\u00eat et de s'assurer que la s\u00e9quence d'appels de la fonction arrivera \u00e0 la condition d'arr\u00eat.<\/p>\n<p>Dans l'exercice suivant, la condition d'arr\u00eat a d\u00e9j\u00e0 \u00e9t\u00e9 d\u00e9finie pour vous mais vous devez \u00e9crire le reste de la fonction r\u00e9cursive.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform6\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox6'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Somme digitale<\/span><\/div>La<em> somme digitale<\/em> d'une nombre <code>n<\/code> est la somme de ces chiffres. Ecrivez une fonction r\u00e9cursive <code>sommeDigital(n)<\/code>\u00a0qui prend en entr\u00e9e un nombre positif\u00a0<code>n<\/code>\u00a0et retourne sa somme digitale. Par exemple, <code>sommeDigital(2019)<\/code>\u00a0retournera 12 car 2+0+1+9=12. <a class=\"hintlink\"  id=\"hintlink7\">Indice #1<\/a>\u00a0<a class=\"hintlink\"  id=\"hintlink8\">Indice #2<\/a><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode6' id='usercode6'  cols=10 rows=20   class='pyboxCode RW'>\ndef sommeDigital(n):\n  if n &lt; 10:\n return n\n else:\n # recursive case\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory6' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput6\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<input type='hidden' id='defaultCode6' value='def sommeDigital(n):\\n  if n < 10:\\n return n\\n else:\\n # recursive case\\n'><\/input>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit6' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch6\" value=\"Input Switch\" onclick=\"pbInputSwitch(6,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(6)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(6,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect6' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(6,'16.digitalsum')\" >History<\/option>\n<option name='default' data-pbonclick=\"pbSetText(6,descape($('#defaultCode6').val()))\" >Reset code to default<\/option>\n<option name='help' data-pbonclick=\"helpClick(6);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse6\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"6\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"ca8c378d463e848b9a27010f28d70ba4\"\/>\n<div id='pbresults6' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(6);});pbInputSwitch(6,\"Y\");<\/script>\n<\/p>\n<p>Maintenant vous allez \u00e9crire une fonction qui appelle la fonction r\u00e9cursive\u00a0<code>sommeDigital<\/code>\u00a0comme sous-fonction.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform9\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox9'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Racine digitale<\/span><\/div>La racine digitale d'un entier non-n\u00e9gatif\u00a0<code>n<\/code>\u00a0est calcul\u00e9e de la mani\u00e8re suivante. Commencez par additionner tous les chiffres de\u00a0<code>n<\/code>. Les chiffres du r\u00e9sultat de cette somme sont ensuite ajout\u00e9 et le processus continue jusqu'\u00e0 ce que l'on obtienne un r\u00e9sultat \u00e0 un seul chiffre. Par exemple, la racine digitale de 2019 est 3 car 2+0+1+9=12 et 1+2=3. Ecrivez une fonction r\u00e9cursive\u00a0<code>racineDigitale(n)<\/code>\u00a0qui retourne la racine digitale de\u00a0<code>n<\/code>.<br\/><strong>Assumez<\/strong>\u00a0que vous avez \u00e0 disposition la fonction\u00a0<code>sommeDigitale<\/code>.<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode9' id='usercode9'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory9' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput9\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit9' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch9\" value=\"Input Switch\" onclick=\"pbInputSwitch(9,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(9)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(9,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect9' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(9,'16.digitalroot')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(9);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse9\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"9\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"7a7a1785c8cf3a841820e75e47d55044\"\/>\n<div id='pbresults9' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(9);});pbInputSwitch(9,\"Y\");<\/script>\n<\/p>\n<h1>Exercices<\/h1>\n<div class='pybox modeNeutral' id='pybox10'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Short Answer Exercise: <\/span><span class='title'>PGCD<\/span><\/div>Quelle est la sortie de ce programme r\u00e9cursif?<\/p>\n<pre>def pgcd(a, b):\r\n  if b == 0: return a\r\n  return pgcd(b, a % b)\r\nprint(pgcd(20, 12))<\/pre><label for=\"pyShortAnswer10\">Your answer (enter a number): <\/label><input type=\"text\" onkeypress=\"{if (event.keyCode==13) pbShortCheck(10)}\" id=\"pyShortAnswer10\"><div class=\"pyboxbuttons\"><input type=\"hidden\" name=\"type\" value=\"number\"\/><input type=\"hidden\" name=\"correct\" value=\"4\"\/><input type=\"hidden\" name=\"slug\" value=\"16.shortgcd\"\/><input type=\"hidden\" name=\"lang\" value=\"\"\/><input type='submit' style='margin:5px;' value='Check answer' onClick = 'pbShortCheck(10)'\/><\/div><div class=\"pbresults\" id=\"pyShortResults10\"><\/div><div class=\"epilogue\">Correct! Ce programme remarquablement court calcule le \"pgcd\" (plus grand commun diviseur) de deux nombres. Ceci est connu comme <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_d%27Euclide\">l'algorithme d'Euclide<\/a>, l'un des plus anciens algorithmes connus.<\/div><\/div>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform11\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox11'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Gr\u00ealon<\/span><\/div>Une suite de gr\u00ealon commen\u00e7ant avec un nombre positif\u00a0<code>n<\/code>\u00a0est g\u00e9n\u00e9r\u00e9e en appliquant les deux r\u00e8gles suivantes. Si\u00a0<code>n<\/code>\u00a0est paire, le nombre suivant dans le s\u00e9rie est\u00a0<code>n\/2<\/code>. Si\u00a0<code>n<\/code>\u00a0est impair, le nombre suivante dans la \u00a0s\u00e9rie est\u00a0<code>3*n+1<\/code>. En r\u00e9p\u00e9tant ce processus, on g\u00e9n\u00e8re la s\u00e9quence de gr\u00ealon. Ecrivez une fonction r\u00e9cursive\u00a0<code>grelon(n)<\/code>\u00a0qui affiche la s\u00e9quence de gr\u00ealon commen\u00e7ant \u00e0\u00a0<code>n<\/code>. Arr\u00eatez quand la s\u00e9quence arrive \u00e0 1\u00a0(sinon la s\u00e9quence boucle ind\u00e9finiment 1, 4, 2, 1, 4, 2, ...) <br\/> Par exemple quand <code>n=5<\/code>, votre programme doit afficher la suite:<\/p>\n<pre>5\r\n16\r\n8\r\n4\r\n2\r\n1<\/pre><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode11' id='usercode11'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory11' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput11\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit11' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch11\" value=\"Input Switch\" onclick=\"pbInputSwitch(11,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(11)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(11,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect11' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(11,'16.hailstone')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(11);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse11\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"11\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"f7386e4d5aa863b89e771e45ede9a81c\"\/>\n<div id='pbresults11' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(11);});pbInputSwitch(11,\"Y\");<\/script>\n<\/p>\n<p>Les math\u00e9maticiens pensent que toutes les s\u00e9quences de gr\u00ealon atteignent 1, quelque soit la valeur de\u00a0<code>n<\/code>\u00a0avec laquelle on commence. Cependant, personne n'a pu le prouver jusqu'\u00e0 aujourd'hui.<\/p>\n<h2>Listes imbriqu\u00e9es<\/h2>\n<p>Nous discutons maintenant une application int\u00e9ressante et naturelle de la r\u00e9cursivit\u00e9. Une liste <em>imbriqu\u00e9e<\/em> est une liste avec quelques listes \u00e0 l'int\u00e9rieur des autres, peut-\u00eatre plusieurs fois. Par exemple, certaines listes imbriqu\u00e9es d'entiers sont <code>[[1, 2], [9, 10]]<\/code> en plus de <code>[[1], 2]<\/code> et <code>x\u00a0= [[1], 2, [3, [[4]]]]<\/code>. L'exemple liste imbriqu\u00e9e derni\u00e8re est une liste de trois \u00e9l\u00e9ments: <code>x[0]==[1]<\/code> \u00e0 commencer, ensuite <code>x[1]==2<\/code>, et <code>x[2]==[3, [[4]]]<\/code>. (Par cons\u00e9quent <code>len(x)=3<\/code>.) Notez qu'une liste comme <code>[1, 2, 3]<\/code>\u00a0est \u00e9galement consid\u00e9r\u00e9e comme une liste imbriqu\u00e9e.\u00a0<strong>Peut-on \u00e9crire une fonction pour trouver la somme totale de <em>n'importe quelle<\/em> liste imbriqu\u00e9e des entiers?<\/strong> Par exemple, pour donn\u00e9e <code>[[5], 2, [10, 8, [[7]]]]<\/code> il doit retourner la valeur <code>32<\/code>.<\/p>\n<p>Cette t\u00e2che est difficile pour une boucle <code>while<\/code> ou <code>for<\/code>, puisque nous voulons une fonction qui peut prendre des listes imbriqu\u00e9es avec n'importe quelle forme\/format. Toutefois, les listes imbriqu\u00e9es ont une structure naturellement r\u00e9cursive: <em>une liste imbriqu\u00e9e est une liste dont chacune des pi\u00e8ces est (a) un nombre entier ou (b) une liste imbriqu\u00e9e<\/em>. Et, lorsque l'on calcule la somme de chaque sous-partie de la liste principale, le total de ces valeurs correspond \u00e0 la somme globale. Nous pouvons exprimer cela avec le code suivant; il utilise <code>isinstance(x, int)<\/code> qui nous donne une valeur bool\u00e9enne indiquant si <code>x<\/code> est de type entier (par opposition \u00e0 une liste).<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform12\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox12'>\n<div class=\"heading\"><span class='type'>Example: <\/span><span class='title'>Sommant une liste imbriqu\u00e9e<\/span><\/div>Le calcul de la somme des \u00e9l\u00e9ments dans une liste imbriqu\u00e9e avec une fonction r\u00e9cursive. Une fois que vous appuyez sur <strong>Ex\u00e9cuter<\/strong>, vous verrez sa valeur sur certains tests.<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 214px;'><textarea wrap='off' name='usercode12' id='usercode12'  cols=10 rows=8 readonly='readonly'  style = 'height : 214px;'  class='pyboxCode RO'>\ndef listeImbriqueeSomme(LI):\n    if isinstance(LI, int):     # (a): LI est un nombre entier\n        return LI               # cas de base\n\n    somme = 0                   # (b): LI est une liste des listes imbriquees\n    for i in range(0, len(LI)): # ajouter chaque partie de la liste principale\n        somme = somme + listeImbriqueeSomme(LI[i])\n    return somme                # tout est fait<\/textarea><\/div>\n<div id='pbhistory12' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput12\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit12' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch12\" value=\"Input Switch\" onclick=\"pbInputSwitch(12,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(12)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(12,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse12\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"12\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"4aa6b50ef2512b7c8a0d162efe299cfb\"\/>\n<div id='pbresults12' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(12,\"Y\");<\/script>\n<\/p>\n<p>Voyez-vous comment la r\u00e9cursivit\u00e9 est utilis\u00e9e pour d\u00e9composer chaque liste imbriqu\u00e9e en parties plus petites? Par exemple, <code>listeImbriqueeSomme([1, [3, 4], 5])<\/code> fait un total de 6 appels r\u00e9cursifs: la premi\u00e8re, puis sur <code>1<\/code>, puis sur <code>[3, 4]<\/code>, puis sur <code>3<\/code> et sur <code>4<\/code>, (apr\u00e8s laquelle la somme <code>[3, 4]<\/code> est retourn\u00e9 comme <code>7<\/code>) et enfin sur <code>5<\/code> (apr\u00e8s laquelle le montant global <code>13<\/code> est obtenu).<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform13\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox13'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Recherchant dans une liste imbriqu\u00e9e<\/span><\/div>En \u00e9crivant quelque chose qui ressemble <code>listeImbriqueeSomme<\/code>, d\u00e9finir une fonction r\u00e9cursive<\/p>\n<pre>listeImbriqueeContient(LI, cible)<\/pre>qui prend une liste imbriqu\u00e9e <code>LI<\/code> des entiers et un entier <code>cible<\/code>, et indique si <code>cible<\/code> est contenu n'importe o\u00f9 dans la liste imbriqu\u00e9e. Votre code doit retourner la valeur bool\u00e9enne <code>True<\/code> quand elle est contenue dans la liste imbriqu\u00e9e, et <code>False<\/code> autement. <br\/> Par exemple, <code>listeImbriqueeContient([1, [2, [3], 4]], 3)<\/code> devrait donner <code>True<\/code> et <code>listeImbriqueeContient([1, [2, [3], 4]], 5)<\/code> devrait donner <code>False<\/code>.<div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode13' id='usercode13'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory13' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput13\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit13' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch13\" value=\"Input Switch\" onclick=\"pbInputSwitch(13,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(13)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(13,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect13' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(13,'17.nestedFind')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(13);\" >Help<\/option>\n<\/select><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse13\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"13\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"e6b98bd77979ba8f01a688d52b0aec32\"\/>\n<div id='pbresults13' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(13);});pbInputSwitch(13,\"Y\");<\/script>\n<\/p>\n<h2>R\u00e8gle d'or<\/h2>\n<p>La r\u00e9cursion est aussi li\u00e9e aux fractales - des images qui contiennent de multiples copies d'elle-m\u00eame. La banni\u00e8re en haut de cette page en est un exemple. Le prochain exercice cr\u00e9e un motif r\u00e9p\u00e9t\u00e9 simple qui utilise la r\u00e9cursion.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform14\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox14'>\n<img title='You have not yet completed this problem.' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>R\u00e8gle fractale<\/span><\/div>Mettez dans l'ordre les lignes de code pour cr\u00e9er un programme qui produit un dessin r\u00e9cursif de type r\u00e8gle. Par exemple, pour\u00a0<code>n=3<\/code>\u00a0le programme devrait afficher.<\/p>\n<pre>-\r\n--\r\n-\r\n---\r\n-\r\n--\r\n-<\/pre><ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble14\">\n <li class=\"pyscramble\">   print(&#039;-&#039;)<\/li>\n <li class=\"pyscramble\">   regle(n - 1)<\/li>\n <li class=\"pyscramble\">  else:<\/li>\n <li class=\"pyscramble\">  if n == 1:<\/li>\n <li class=\"pyscramble\">   print(n * &#039;-&#039;)<\/li>\n <li class=\"pyscramble\">   regle(n - 1)<\/li>\n <li class=\"pyscramble\">def regle(n):<\/li>\n<\/ul>\n<input type='hidden' id='usercode14' name='usercode14'\/>\n<div id='pbhistory14' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit14' value=' '\/><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"\"\/><input type=\"hidden\" id=\"inputInUse14\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"14\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"8ff46e6e24131c4c89e27f8290ad4c61\"\/>\n<div id='pbresults14' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit14\").value = \"Run program\";document.getElementById(\"inputInUse14\").value = \"N\";<\/script>\n<\/p>\n<p>Bravo! Vous pouvez passer \u00e0 la prochaine le\u00e7on.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Nous avons vu que les fonctions nous permettent d'organiser et de r\u00e9utiliser des parties de notre code. Nous avons vu \u00e9galement que les fonctions peuvent \u00eatre d\u00e9finies \u00e0 partir d'autres fonctions. Dans cette le\u00e7on, nous allons apprendre qu'une fonction peut &hellip; <a href=\"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/16-fr\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4693","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4693","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/comments?post=4693"}],"version-history":[{"count":33,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4693\/revisions"}],"predecessor-version":[{"id":10725,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/4693\/revisions\/10725"}],"wp:attachment":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/media?parent=4693"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}