{"id":1973,"date":"2011-06-08T16:37:44","date_gmt":"2011-06-08T16:37:44","guid":{"rendered":"http:\/\/cemclinux1.math.uwaterloo.ca\/~cscircles\/wordpress\/?page_id=1973"},"modified":"2011-06-08T16:37:44","modified_gmt":"2011-06-08T16:37:44","slug":"16-recursion","status":"publish","type":"page","link":"https:\/\/olescs.hkmu.edu.hk\/python\/16-recursion\/","title":{"rendered":"16: Recursion"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nOriginal lesson author: Graeme Kemkes, gdkemkes@alumni.uwaterloo.ca, http:\/\/cscircles.ca<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/-->\n<p>We have seen that functions allow us to organize and re-use parts of our code. We have also seen that functions can be defined in terms of other functions. In this lesson we learn that a function can be defined in terms of itself! This very useful approach is called <em>recursion<\/em>.\u00a0Legend has it that \"to understand recursion, you must first understand recursion.\"<\/p>\n<h1>Example<\/h1>\n<p>In our lesson on loops, we used a\u00a0<code>while<\/code>\u00a0loop to create the following output.<\/p>\n<pre>5\n4\n3\n2\n1\nBlastoff!<\/pre>Here is a program that uses recursion to achieve the same effect.<\/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>A countdown using recursion<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 countdown(n):\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    countdown(n - 1)\n\ncountdown(5)<\/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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"fb83afad73e49bd03eb146e614438f7c\"\/>\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>Let's add some extra print statements to help us understand how the program works. This version of the program also reads the time limit from input.<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>A countdown using recursion<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 countdown(n):\n  print('Entering countdown(',n,')')\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    countdown(n - 1)\n  print('Exiting from countdown(',n,')')\n\nlimit = int(input())\ncountdown(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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"05187437d86d37a181341f0ec0c7c999\"\/>\n<div id='pbresults1' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(1,\"N\");<\/script>\n<\/p>\n<p>If you like, use\u00a0<strong>Enter input<\/strong>\u00a0with the above program to try other input values. Try\u00a0<code>0<\/code>\u00a0first and see what happens, and then\u00a0<code>1<\/code>.<\/p>\n<p>When the input is <code>5<\/code>,\u00a0the program first calls a copy of the\u00a0<code>countdown<\/code>\u00a0function with\u00a0<code>n=5<\/code>, which prints\u00a0<code>5<\/code>\u00a0and calls\u00a0<code>countdown(4)<\/code>.\u00a0This continues until <code>countdown(0)<\/code>, which prints\u00a0<code>\"Blastoff!\"<\/code>\u00a0and does not call <code>countdown<\/code> any more. When Python finishes executing the\u00a0<code>n=0<\/code>\u00a0call of the <code>countdown<\/code>\u00a0function, Python returned to the function that called it, which is the\u00a0<code>n=1<\/code>\u00a0call of the\u00a0<code>countdown<\/code>. Then we return to the <code>n=2<\/code>\u00a0call, and so on.<\/p>\n<p>To double-check our understanding, we can also visualize the recursive code:<\/p>\n<p><iframe width='100%' height='480' frameborder='0' scrolling='no' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/OnlinePythonTutor3-cemc\/iframe-embed.html#code=def+countdown%28n%29%3A%0A++if+n+%3D%3D+0%3A%0A++++print%28%27Blastoff%21%27%29%0A++else%3A%0A++++print%28n%29%0A++++countdown%28n+-+1%29%0A%0Acountdown%283%29&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=3&curInstr=0&resizeContainer=true&highlightLines&width=400&rightStdout=1'><\/iframe><\/p>\n<p>The new twist, which makes recursion unique from the functions we've seen before, is that multiple versions of the function are running at the same time. That is to say, there is more than one frame at a time corresponding to the same function. This is pretty much the same as <a href=\"http:\/\/cscircles.cemc.uwaterloo.ca\/10-def\/#funcfunc\">what we saw in the visualization where one function called another<\/a>, except now the calling function is the same as the function being called. However, you have to be careful to note that at each step, only the \"current\" variables (the newest\/bottom-most frame) are really used\u00a0\u2014 the non-bottom frames are \"paused\" and their variables inaccessible.<\/p>\n<p>Now it's your turn to write some code. Modify the\u00a0<code>countdown<\/code>\u00a0function so that it counts up instead of down.<\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Blast Up<\/span><\/div>Write a recursive function\u00a0<code>countup(n)<\/code>\u00a0which prints 'Blastoff!' followed by the numbers\u00a0<code>1<\/code>\u00a0to\u00a0<code>n<\/code>\u00a0on separate lines. <a class=\"hintlink\"  id=\"hintlink3\">Hint<\/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 countdown(n):\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    countdown(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 countdown(n):\\n  if n == 0:\\n    print(\\u0027Blastoff!\\u0027)\\n  else:\\n    print(n)\\n    countdown(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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"c80791b162429ab17543828679673713\"\/>\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>Next, let's modify our\u00a0<code>countdown<\/code>\u00a0program to count in increments of 2. The output should be 5, 3, 1, Blastoff! We will change the function argument from\u00a0<code>n-1<\/code>\u00a0to\u00a0<code>n-2<\/code>. Is there anything else that we need to change?<\/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>Trying to count down in increments of 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 countdownBy2(n):\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    countdownBy2(n - 2)\n\ncountdownBy2(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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"33f97a92cecd10ba94680c59d48b6f7c\"\/>\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>You can see that this program did not work as we intended. It printed\u00a0<code>5, 3, 1<\/code>, like we wanted, but instead of stopping it continued with\u00a0<code>-1, -3, -5<\/code>\u00a0and ran forever. (More precisely, it runs out of time and memory, because each recursive call takes up a little more working memory; see <a href=\"http:\/\/cscircles.cemc.uwaterloo.ca\/visualize\/#code=def%20countdownBy2(n)%3A%0A%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20print('Blastoff!')%0A%20%20else%3A%0A%20%20%20%20print(n)%0A%20%20%20%20countdownBy2(n%20-%202)%0A%0AcountdownBy2(5)\">the same example in the visualizer<\/a>.)<\/p>\n<p>When designing a recursive function, we must be careful that its sequence of calls does not continue forever!\u00a0Modify the <code>countdownBy2<\/code> program above so that it correctly stops at 1 (or 2, if\u00a0<code>n<\/code>\u00a0is even) and prints 'Blastoff!'.<\/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:\/\/olescs.hkmu.edu.hk\/python\/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>Modify this recursive program to correctly count down in increments of 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 countdownBy2(n):\n  if n == 0:\n    print('Blastoff!')\n  else:\n    print(n)\n    countdownBy2(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 countdownBy2(n):\\n  if n == 0:\\n    print(\\u0027Blastoff!\\u0027)\\n  else:\\n    print(n)\\n    countdownBy2(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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse5\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"5\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"a0d30268364f5b9dadb8a2727df0bf57\"\/>\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>Designing recursive functions<\/h1>\n<p>A <em>recursive function<\/em> just means a function that calls itself. But there must be some occasions when the function does not call itself, or else the program will run forever, like we saw above. A\u00a0<strong>base case<\/strong>\u00a0is the part of a recursive function where it doesn't call itself. In the example above, the base case was\u00a0<code>n&lt;=0<\/code>. Designing a recursive function requires that you carefully choose a base case and make sure that every sequence of function calls eventually reaches a base case.<\/p>\n<p>In the next exercise, the base case has been programmed for you, but you will write the rest of the recursive function.<\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Digital Sum<\/span><\/div>The <em>digital sum<\/em>\u00a0of a number <code>n<\/code> is the sum of its digits.\u00a0Write a recursive function\u00a0<code>digitalSum(n)<\/code>\u00a0that takes a positive integer <code>n<\/code> and returns its digital sum. For example,\u00a0<code>digitalSum(2019)<\/code>\u00a0should return 12 because 2+0+1+9=12. <a class=\"hintlink\"  id=\"hintlink7\">Hint #1<\/a>\u00a0<a class=\"hintlink\"  id=\"hintlink8\">Hint #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 digitalSum(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 digitalSum(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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse6\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"6\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"e6b1dd83ec1061d1757f55e5b6ab4cad\"\/>\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>Now you will write a recursive function that calls\u00a0<code>digitalSum<\/code> as a subroutine.<\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Digital Root<\/span><\/div>The digital root of a non-negative integer\u00a0<code>n<\/code>\u00a0is computed as follows. Begin by summing the digits of\u00a0<code>n<\/code>. The digits of the resulting number are then summed, and this process is continued until a single-digit number is obtained. For example, the digital root of 2019 is 3 because 2+0+1+9=12 and 1+2=3. Write a recursive function\u00a0<code>digitalRoot(n)<\/code>\u00a0which returns the digital root of\u00a0<code>n<\/code>.<br\/><strong>Assume<\/strong>\u00a0that a working definition of <code>digitalSum<\/code> will be provided for your program.<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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse9\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"9\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"5d82584450af467b5e7a2f032e729187\"\/>\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>Exercises<\/h1>\n<div class='pybox modeNeutral' id='pybox10'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Short Answer Exercise: <\/span><span class='title'>GCD<\/span><\/div>What is the output of the following recursive program? <\/p>\n<pre>def gcd(a, b):<br\/> \u00a0if b == 0: return a<br\/> \u00a0return gcd(b, a % b)<br\/>print(gcd(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=\"en-US\"\/><input type='submit' style='margin:5px;' value='Check answer' onClick = 'pbShortCheck(10)'\/><\/div><div class=\"pbresults\" id=\"pyShortResults10\"><\/div><div class=\"epilogue\">Correct! This remarkably short program computes the <strong>g<\/strong>reatest <strong>c<\/strong>ommon <strong>d<\/strong>ivisor of two numbers. This is known as the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Euclidean_algorithm\">Euclidean Algorithm<\/a>, one of the oldest known algorithms.<\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Hailstone<\/span><\/div>The\u00a0<em>hailstone sequence<\/em>\u00a0starting at a positive integer\u00a0<code>n<\/code>\u00a0is generated by following two simple rules. If\u00a0<code>n<\/code>\u00a0is even, the next number in the sequence is\u00a0<code>n\/2<\/code>. If\u00a0<code>n<\/code>\u00a0is odd, the next number in the sequence is\u00a0<code>3*n+1<\/code>. Repeating this process, we generate the hailstone sequence. Write a recursive function\u00a0<code>hailstone(n)<\/code>\u00a0which prints the hailstone sequence beginning at <code>n<\/code>. Stop when the sequence reaches the number\u00a0<code>1<\/code>\u00a0(since otherwise, we would loop forever 1, 4, 2, 1, 4, 2, ...) <br\/> For example, when\u00a0<code>n=5<\/code>, your program should output the following sequence: <\/p>\n<pre>5<br\/>16<br\/>8<br\/>4<br\/>2<br\/>1<\/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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse11\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"11\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"2e072b9c8038a1aeeffb97db6b7f721a\"\/>\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>Mathematicians believe that every hailstone sequence reaches\u00a0<code>1<\/code>\u00a0eventually, no matter what value of\u00a0<code>n<\/code>\u00a0we start with. However, no one has been able to prove this yet.<\/p>\n<h2>Nested Lists<\/h2>\n<p>Here is an interesting natural application of recursion. A <em>nested list<\/em> is one where you put some lists inside of others, possibly multiple times. For example, some nested lists of integers are <code>[[1, 2], [9, 10]]<\/code> as well as <code>[[1], 2]<\/code> and <code>x\u00a0= [[1], 2, [3, [[4]]]]<\/code>. The last nested list example is a list with three elements: <code>x[0]==[1]<\/code> to begin, then <code>x[1]==2<\/code>, then <code>x[2]==[3, [[4]]]<\/code>. (So <code>x<\/code>, viewed as a list, has length 3). Note that a list like <code>[1, 2, 3]<\/code>\u00a0also counts as a nested list.\u00a0<strong>Can we write a function to find the total sum of\u00a0<em>any<\/em> nested list of integers?\u00a0<\/strong>For example, on input <code>[[5], 2, [10, 8, [[7]]]]<\/code> it should return the value <code>32<\/code>.<\/p>\n<p>This task is difficult for a <code>while<\/code> loop or a <code>for<\/code> loop, since we want a function that works on nested lists with any shape\/format. However, nested lists have a naturally recursive structure: <em>a nested list is a list each of whose items is either (a) an integer or (b) a nested list<\/em>. And, once we compute the sum of each subpart of the main list, the total of those values is the overall sum. We can express this with the following code; it uses <code>isinstance(x, int)<\/code> which gives a boolean value telling us whether <code>x<\/code> has integer type (as opposed to a list).<\/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'>Summing a Nested List<\/span><\/div>Computing the sum of the elements in a nested list with a recursive function. Once you press <strong>Run<\/strong> you will see its value on some 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 nestedListSum(NL):\n    if isinstance(NL, int):     # case (a): NL is an integer\n        return NL               # base case\n\n    sum = 0                     # case (b): NL is a list of nested lists\n    for i in range(0, len(NL)): # add subsums from each part of the main list\n        sum = sum + nestedListSum(NL[i])\n    return sum                  # all done<\/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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse12\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"12\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"e05466733f9098e2816e0bd8c90ff497\"\/>\n<div id='pbresults12' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(12,\"Y\");<\/script>\n<\/p>\n<p>Recursion is used to break down each nested list into smaller parts. For example, <code>nestedListSum([1, [3, 4], 5])<\/code> makes a total of 6 recursive calls: the initial one, then on <code>1<\/code>, then on <code>[3, 4]<\/code>, then on <code>3<\/code>, then <code>4<\/code>, (after which the <code>[3, 4]<\/code> total is returned as <code>7<\/code>) and finally on <code>5<\/code> (after which the overall total <code>13<\/code> is obtained). Here is the same code in the visualizer.<\/p>\n<p><iframe width='100%' height='480' frameborder='0' scrolling='no' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/OnlinePythonTutor3-cemc\/iframe-embed.html#code=def+nestedListSum%28NL%29%3A%0A++if+isinstance%28NL%2C+int%29%3A%0A++++return+NL%0A%0A++sum+%3D+0%0A++for+i+in+range%280%2C+len%28NL%29%29%3A%0A++++sum+%3D+sum+%2B+nestedListSum%28NL%5Bi%5D%29%0A++return+sum%0A%0A%23+some+examples%0AnestedListSum%28129%29%0AnestedListSum%28%5B400%2C+50%2C+6%5D%29%0AnestedListSum%28%5B%5B1%2C+2%5D%2C+%5B3%2C+4%5D%2C+5%5D%29%0AnestedListSum%28%5B%5B1%2C+%5B2%2C+3%5D%2C+4%2C+5%5D%5D%29&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=3&curInstr=0&resizeContainer=true&highlightLines&width=400&rightStdout=1'><\/iframe><\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Searching a Nested List<\/span><\/div>By writing something similar to <code>nestedListSum<\/code>, define a recursive function <\/p>\n<pre>nestedListContains(NL, target)<\/pre> that takes a nested list <code>NL<\/code> of integers and an integer <code>target<\/code>, and indicates whether <code>target<\/code> is contained anywhere in the nested list. Your code should return the boolean value <code>True<\/code> when it is contained in the nested list, and <code>False<\/code> if it is not contained in it.<br\/>For example, <code>nestedListContains([1, [2, [3], 4]], 3)<\/code> should give <code>True<\/code> and <code>nestedListContains([1, [2, [3], 4]], 5)<\/code> should give <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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse13\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"13\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"2b8315b3bdd904d8e227109f389e8aeb\"\/>\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>This Rules<\/h2>\n<p>Recursion is also related to fractals \u2014\u00a0images which contain multiple smaller copies of themselves. The banner at the top of this webpage is one example. The next exercise creates a simple repeating pattern using recursion.<\/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:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>Fractal Ruler<\/span><\/div>Unscramble the lines to create a program that produces a recursive ruler-like design. For example, when\u00a0<code>n=3<\/code>\u00a0the program should output the following design. <\/p>\n<pre>-<br\/>--<br\/>-<br\/>---<br\/>-<br\/>--<br\/>-<\/pre> <ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble14\">\n <li class=\"pyscramble\">  else:<\/li>\n <li class=\"pyscramble\">   print(n * &#039;-&#039;)<\/li>\n <li class=\"pyscramble\">  if n == 1:<\/li>\n <li class=\"pyscramble\">   ruler(n - 1)<\/li>\n <li class=\"pyscramble\">   print(&#039;-&#039;)<\/li>\n <li class=\"pyscramble\">def ruler(n):<\/li>\n <li class=\"pyscramble\">   ruler(n - 1)<\/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=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse14\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"14\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"59abcbc14d1da6ffd9fa45fa4391fda2\"\/>\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>Congratulations! You are ready to move to the next lesson.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We have seen that functions allow us to organize and re-use parts of our code. We have also seen that functions can be defined in terms of other functions. In this lesson we learn that a function can be defined &hellip; <a href=\"https:\/\/olescs.hkmu.edu.hk\/python\/16-recursion\/\">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-1973","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/1973"}],"collection":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/comments?post=1973"}],"version-history":[{"count":0,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/1973\/revisions"}],"wp:attachment":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/media?parent=1973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}