{"id":6175,"date":"2012-11-05T20:36:57","date_gmt":"2012-11-06T01:36:57","guid":{"rendered":"http:\/\/cscircles.cemc.uwaterloo.ca\/?page_id=6175"},"modified":"2020-10-26T01:15:37","modified_gmt":"2020-10-26T05:15:37","slug":"16-recursion-nl","status":"publish","type":"page","link":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/16-recursion-nl\/","title":{"rendered":"16: Recursie"},"content":{"rendered":"<p>We hebben gezien dat functies ons in staat stellen om een programma beter te organiseren en delen ervan opnieuw te gebruiken. We hebben ook gezien dat functies kunnen worden gedefinieerd met behulp van andere functies. In deze les zullen we zien dat functies kunnen worden gedefinieerd met behulp van zichzelf! Dit fenomeen wordt <em>recursie<\/em> genoemd. De legende zegt dat \"om recursie te begrijpen, je eerst recursie moet begrijpen\".<\/p>\n<h1>Voorbeeld<\/h1>\n<p>In onze les over loops hebben we een&nbsp;<code>while<\/code>&nbsp;loop gebruikt om de volgende output te genereren.<\/p>\n<pre>5\n4\n3\n2\n1\nBoemm!<\/pre>Hier volgt een programma dat recursie gebruikt om hetzelfde effect te bereiken.<\/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>Een countdown door middel van recursie<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('Boemm!')\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=\"\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"53e1a973697237d71b06db32584d4a6f\"\/>\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>Laten we wat extra print statements gebruiken om ons te helpen het programma te begrijpen. Deze versie leest ook de tijd in vanuit 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>Een countdown die gebruik maakt van recursie<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('Starten countdown(',n,')')\n  if n == 0:\n    print('Boemm!')\n  else:\n    print(n)\n    countdown(n - 1)\n  print('Verlaten van 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=\"\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"fa5653211b0feca609cf23a77d9a576e\"\/>\n<div id='pbresults1' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(1,\"N\");<\/script>\n<\/p>\n<p>Je kunt&nbsp;<strong>Enter input<\/strong>&nbsp;gebruiken om andere input waarden uit te proberen. Probeer eerst&nbsp;<code>0<\/code>, kijk wat er gebeurt, en probeer dan <code>1<\/code>.<\/p>\n<p>Wanneer de input <code>5<\/code> is,&nbsp;zal het programma eerst een kopie van de <code>countdown<\/code>-functie aanroepen met&nbsp;<code>n=5<\/code>. Deze zal&nbsp;<code>5<\/code>&nbsp;printen en <code>countdown(4)<\/code> aanroepen.&nbsp;Dit gaat zo door totdat <code>countdown(0)<\/code> wordt aangeroepen, en die print&nbsp;<code>\"Boemm!\"<\/code>. Vervolgens zal de functie niet langer <code>countdown<\/code> aanroepen. Wanneer Python stopt met het uitvoeren van de <code>n=0<\/code>-aanroep van de <code>countdown<\/code>&nbsp;functie, gaan we terug naar de functie die hem aanriep, namelijk de <code>n=1<\/code>-aanroep van&nbsp;<code>countdown<\/code>. Vanaf daar gaan we terug naar de <code>n=2<\/code>-aanroep, enzovoort.<\/p>\n<p>Om nog even te checken of we het begrijpen zullen we het programma met recursie nog eens stap voor stap bekijken:<br \/>\n<iframe width='100%' height='480' frameborder='0' scrolling='no' src='https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-content\/plugins\/pybox\/OnlinePythonTutor3-cemc\/iframe-embed.html#code=def+countdown%28n%29%3A%0A++if+n%3D%3D0%3A%0A++++print%28%27Boemm%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=450&rightStdout=1'><\/iframe><\/p>\n<p>Nieuw is, en dat maakt recursieve functies uniek ten opzichte van eerdere functies, dat meerdere versies van dezelfde functie tegelijkertijd in actie zijn. Dat lijkt veel op wat we zagen in <a href=\"http:\/\/cscircles.cemc.uwaterloo.ca\/10-def-nl\/\">Les 10<\/a> waar ook de ene functie de andere aanriep, behalve dan dat hier de functie zichzelf aanroept. Merk op dat bij elke stap alleen de op dat moment aanwezige variabelen worden gebruikt en niet de variabelen in de eerder aangeroepen functies. Die variabele staan 'op pauze'.<\/p>\n<p>Het is nu aan jou om een programma te (her)schrijven. Pas de&nbsp;<code>countdown<\/code>-functie aan zodat het niet aftelt (van boven naar beneden) maar optelt telt (van beneden naar boven).<\/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'>Boemm na omhoog tellen<\/span><\/div>Schrijf een recursieve functie&nbsp;<code>countup(n)<\/code>&nbsp;die 'Boemm!' afdrukt gevolgd door de getallen&nbsp;<code>1<\/code>&nbsp;tot&nbsp;<code>n<\/code>&nbsp;op gescheiden regels. <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=\"\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"de4e20bc70b8088c9c200eff16aae4c5\"\/>\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>Pas vervolgens het programma&nbsp;<code>countdown<\/code>&nbsp;aan zodanig dat in stappen van 2 wordt geteld. De output moet zijn 5, 3, 1, Boemm! We zullen daarvoor het argument in de functie veranderen van&nbsp;<code>n-1<\/code>&nbsp;in&nbsp;<code>n-2<\/code>. Maar moet er nog meer veranderd worden?<\/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>Poging om af te tellen in stappen van 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('Boemm!')\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=\"\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"2fa448cdda66ddd9bcdcd23dc1a71cb2\"\/>\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>Je kunt zien dat het programma niet werkt zoals bedoeld. Het drukt&nbsp;<code>5, 3, 1<\/code> af zoals bedoeld, maar in plaats van te stoppen gaat het verder met&nbsp;<code>-1, -3, -5<\/code>&nbsp;en zo gaat het alsmaar door. (Preciezer: na een tijdje raakt de tijd of het geheugen op, omdat elke aanroep bij recursie een beetje extra werkgeheugen vraagt.)<\/p>\n<p>Wanneer we een recursieve functie gebruiken dienen we voorzichtig te zijn dat de aanroepen niet oneindig blijven doorgaan!&nbsp;Pas het <code>countdownBy2<\/code>-programma hierboven aan zodanig dat het stopt bij 1 (of 2, wanneer&nbsp;<code>n<\/code>&nbsp;even is) en print dan 'Boemm!'.<\/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'>Dubbele tijd<\/span><\/div>Pas dit recursieve programma zo aan dat het aftelt in stappen van 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('Boemm!')\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(\\u0027Boemm!\\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=\"\"\/><input type=\"hidden\" id=\"inputInUse5\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"5\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"716e4c3e4eb9fb431678d3487a588178\"\/>\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>Recursieve functies produceren<\/h1>\n<p>Een functie heet <em>recursief<\/em> wanneer de functie zichzelf aanroept. Maar zo'n programma moet niet steeds zichzelf aanroepen, want dan zal het oneindig lang doorlopen, zoals we boven gezien hebben. Een <strong>base case<\/strong>&nbsp;is dat deel van de recursieve functie waarin het zichzelf niet aanroept. In het voorbeeld boven, was de base case&nbsp;<code>n&lt;=0<\/code>. Een recursieve functie ontwerpen vraagt dat je zorgvuldig een base case kiest en dat bij iedere rij van functie aanroepen tenslotte bij deze base case uitkomt.<\/p>\n<p>In de volgende functie is de base case voor jou al geschreven en moet jij de rest van de recursieve functie schrijven.<\/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'>Digital Sum<\/span><\/div>De <em>digitale som<\/em>&nbsp;van een getal <code>n<\/code> is de som van zijn cijfers.&nbsp;Schrijf een recursieve functie&nbsp;<code>digitalSum(n)<\/code>&nbsp;dat een positief geheel getal <code>n<\/code> als input heeft en zijn digitale som teruggeeft. Zo geeft code&gt;digitalSum(2019)&nbsp;12 terug omdat 2+0+1+9=12. <a class=\"hintlink\"  id=\"hintlink7\">Hint #1<\/a>&nbsp;<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=\"\"\/><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>Nu zullen we een recursieve functie schrijven dat&nbsp;<code>digitalSum<\/code> aanroept als een 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:\/\/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'>Digital Root<\/span><\/div>De digital root van een niet-negatief geheel getal &nbsp;<code>n<\/code>&nbsp;wordt als volgt berekend. Begin met het optellen van de cijfers van&nbsp;<code>n<\/code>. De cijfers van het resultaat worden opnieuw gesommeerd, en dit proces wordt herhaald tot er maar \u00e9\u00e9n cijfer overblijft. Zo is bijvoorbeeld de digital root van 2019 gelijk aan 3 want 2+0+1+9=12 en 1+2=3. Schrijf een recursieve functie&nbsp;<code>digitalRoot(n)<\/code>&nbsp;die de digital root van <code>n<\/code> terug geeft.<br\/><strong>Neem aan<\/strong>&nbsp;dat een correct werkende versie van <code>digitalSum<\/code> beschikbaar is voor je programma.<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=\"0f08dd3ddf6a5e705b66b4f9175137fc\"\/>\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>Oefeningen<\/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'>GGD<\/span><\/div>Wat is de output van het volgende recursieve programma? <\/p>\n<pre>def ggd(a, b):<br\/>  if b == 0: return a<br\/>  return ggd(b, a % b)<br\/>print(ggd(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! Dit opmerkelijk korte programma berekent de <strong>g<\/strong>rootste <strong>g<\/strong>emene <strong>d<\/strong>eler van twee getallen. Dit staat bekend als het <a href=\"http:\/\/en.wikipedia.org\/wiki\/Euclidean_algorithm.html\">Euclidische algoritme<\/a> , een van de oudst bekende algoritmes.<\/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'>Hagelstenen<\/span><\/div>De <em>hagelsteen-rij<\/em>die begint met een positief getal&nbsp;<code>n<\/code>&nbsp;wordt door de volgende twee eenvoudige regels voortgezet. Als&nbsp;<code>n<\/code>&nbsp;even is, dan is het volgende getal in de rij <code>n\/2<\/code>. Als&nbsp;<code>n<\/code>&nbsp;oneven is, dan is het volgende getal in de rij <code>3*n+1<\/code>. Wanneer we dit proces herhalen dan zetten we de hagelsteen-rij voort. Schrijf een recursieve functie&nbsp;<code>hagelsteen(n)<\/code>&nbsp;die de hagelsteen-rij oplevert, te beginnen met <code>n<\/code>. Stop zodra de rij het getal <code>1<\/code>&nbsp;bereikt (anders zouden we in een oneindige loop terecht komen (1, 4, 2, 1, 4, 2, ...) <br\/> Wanneer we bijvoorbeeld <code>n=5<\/code> invoeren, dan moet je programma de volgende rij produceren:<\/p>\n<pre>5\n16\n8\n4\n2\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=\"eec171a4771e424e18ded4397d7a1448\"\/>\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>Wiskundigen nemen aan dat iedere hagelsteen rij&nbsp;<code>1<\/code> zal bereiken, onafhankelijk van de&nbsp;<code>n<\/code>&nbsp;waarmee we starten. Maar tot nu toe heeft niemand nog het bewijs kunnen leveren.<\/p>\n<p>Recursie is ook verwant aan fractals \u2014&nbsp;plaatjes die steeds meerdere kleiner kopie\u00ebn van zichzelf bevatten. De banner aan de kop dan deze webpagina is er een voorbeeld van. De volgende oefening brengt een eenvoudig zich herhalend patroon voort waarbij recursie gebruikt wordt.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform12\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox12'>\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'>Fractal lijn<\/span><\/div>Zet de regels in de juiste volgorde zodat het resultaat een programma wordt dat als resultaat een zich herhalend ontwerp heeft. Zo geeft voor&nbsp;<code>n=3<\/code>&nbsp;het programma de volgende output. <\/p>\n<pre>-<br\/>--<br\/>-<br\/>---<br\/>-<br\/>--<br\/>-<\/pre> <ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble12\">\n <li class=\"pyscramble\">   print(n * &#039;-&#039;)<\/li>\n <li class=\"pyscramble\">  else:<\/li>\n <li class=\"pyscramble\">   ruler(n - 1)<\/li>\n <li class=\"pyscramble\">def ruler(n):<\/li>\n <li class=\"pyscramble\">   print(&#039;-&#039;)<\/li>\n <li class=\"pyscramble\">  if n == 1:<\/li>\n <li class=\"pyscramble\">   ruler(n - 1)<\/li>\n<\/ul>\n<input type='hidden' id='usercode12' name='usercode12'\/>\n<div id='pbhistory12' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit12' value=' '\/><\/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=\"f846cb2c0c00501e58c00a90954692b3\"\/>\n<div id='pbresults12' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit12\").value = \"Run program\";document.getElementById(\"inputInUse12\").value = \"N\";<\/script>\n<\/p>\n<p>Gefeliciteerd! Je bent klaar om naar de volgende les te gaan.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We hebben gezien dat functies ons in staat stellen om een programma beter te organiseren en delen ervan opnieuw te gebruiken. We hebben ook gezien dat functies kunnen worden gedefinieerd met behulp van andere functies. In deze les zullen we &hellip; <a href=\"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/16-recursion-nl\/\">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-6175","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/6175","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=6175"}],"version-history":[{"count":31,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/6175\/revisions"}],"predecessor-version":[{"id":14197,"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/pages\/6175\/revisions\/14197"}],"wp:attachment":[{"href":"https:\/\/cscircles.cemc.uwaterloo.ca\/dev\/wp-json\/wp\/v2\/media?parent=6175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}