forked from artofproblemsolving/pythonbook
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrecursion.html
More file actions
executable file
·663 lines (560 loc) · 28.7 KB
/
recursion.html
File metadata and controls
executable file
·663 lines (560 loc) · 28.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>11. Recursion — How to Think Like a Computer Scientist: Learning with Python 3 (AoPS Edition)</title>
<link rel="stylesheet" href="_static/style.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="_static/codemirrorEdited.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: './',
VERSION: '1.0',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js"></script>
<script type="text/javascript" src="_static/pywindowCodemirrorC.js"></script>
<script type="text/javascript" src="_static/skulpt.min.js"></script>
<script type="text/javascript" src="_static/skulpt-stdlib.js"></script>
<script type="text/javascript" src="_static/aopsmods.js"></script>
<link rel="copyright" title="Copyright" href="copyright.html" />
<link rel="top" title="How to Think Like a Computer Scientist: Learning with Python 3 (AoPS Edition)" href="index.html" />
<link rel="next" title="12. Classes and Objects — the Basics" href="classes.html" />
<link rel="prev" title="10. Dictionaries" href="dictionaries.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="classes.html" title="12. Classes and Objects — the Basics"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="dictionaries.html" title="10. Dictionaries"
accesskey="P">previous</a> |</li>
<li><a href="index.html">How to Think Like a Computer Scientist: Learning with Python 3 (AoPS Edition)</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="body">
<div class="line-block">
<div class="line"><br /></div>
</div>
<div class="section" id="recursion">
<h1>11. Recursion<a class="headerlink" href="#recursion" title="Permalink to this headline">¶</a></h1>
<p><strong>Recursion</strong> means “defining something in terms of itself” usually at some
smaller scale, perhaps multiple times, to achieve your objective.
For example, we might say “A human being is someone whose mother is a human being”,
or “a directory is a structure that holds files and (smaller) directories”, or “a family tree starts
with a couple who have children, each with their own family sub-trees”.</p>
<p>Programming languages generally support <strong>recursion</strong>, which means that, in order
to solve a problem, functions can <em>call themselves</em> to solve smaller subproblems.</p>
<div class="section" id="drawing-fractals">
<h2>11.1. Drawing Fractals<a class="headerlink" href="#drawing-fractals" title="Permalink to this headline">¶</a></h2>
<p>For our purposes, a <strong>fractal</strong> is a drawing which also has <em>self-similar</em> structure,
where it can be defined in terms of itself.</p>
<p>Let us start by looking at the famous Koch fractal. An order 0 Koch fractal is simply
a straight line of a given size.</p>
<img alt="_images/koch_0.png" src="_images/koch_0.png" />
<p>An order 1 Koch fractal is obtained like this: instead of drawing just one line,
draw instead four smaller segments, in the pattern shown here:</p>
<img alt="_images/koch_1.png" src="_images/koch_1.png" />
<p>Now what would happen if we repeated this Koch pattern again on each of the order 1 segments?
We’d get this order 2 Koch fractal:</p>
<img alt="_images/koch_2.png" src="_images/koch_2.png" />
<p>Repeating our pattern again gets us an order 3 Koch fractal:</p>
<img alt="_images/koch_3.png" src="_images/koch_3.png" />
<p>Now let us think about it the other way around. To draw a Koch fractal
of order 3, we can simply draw four order 2 Koch fractals. But each of these
in turn needs four order 1 Koch fractals, and each of those in turn needs four
order 0 fractals. Ultimately, the only drawing that will take place is
at order 0. This is very simple to code up in Python:</p>
<div id="kochexample" class="pywindow" >
<div id="kochexample_code_div" style="display: block">
<textarea rows="22" id="kochexample_code" class="active_code" prefixcode="undefined">
def koch(t, order, size):
"""
Make turtle t draw a Koch fractal of 'order' and 'size'.
Leave the turtle facing the same direction.
"""
if order == 0: # The base case is just a straight line
t.forward(size)
else:
koch(t, order-1, size/3) # Go 1/3 of the way
t.left(60)
koch(t, order-1, size/3)
t.right(120)
koch(t, order-1, size/3)
t.left(60)
koch(t, order-1, size/3)
import turtle
wn = turtle.Screen()
t = turtle.Turtle()
koch(t, 3, 300)
wn.mainloop()</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['kochexample_code'] = true;
pythonTool.readOnlyFlags['kochexample_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="kochexample_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="kochexample_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="kochexample_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='kochexample_error'></div>
<div style="text-align: center">
<canvas id="kochexample_canvas" class="ac-canvas" height="400" width="600" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="kochexample_suffix" style="display:none">
</pre>
<pre id="kochexample_pre" class="active_out">
</pre>
<div id="kochexample_files" class="ac-files ac-files-hidden"></div>
</div>
<p>The key thing that is new here is that if order is not zero,
<tt class="docutils literal"><span class="pre">koch</span></tt> calls itself recursively to get its job done.</p>
<p>Let’s make a simple observation and tighten up this code. Remember that
turning right by 120 is the same as turning left by -120. So with a
bit of clever rearrangement, we can use a loop instead of lines 10-16:</p>
<div id="kochsimpler" class="pywindow" >
<div id="kochsimpler_code_div" style="display: block">
<textarea rows="13" id="kochsimpler_code" class="active_code" prefixcode="undefined">
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order-1, size/3)
t.left(angle)
import turtle
wn = turtle.Screen()
t = turtle.Turtle()
koch(t, 3, 300)
wn.mainloop()</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['kochsimpler_code'] = true;
pythonTool.readOnlyFlags['kochsimpler_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="kochsimpler_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="kochsimpler_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="kochsimpler_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='kochsimpler_error'></div>
<div style="text-align: center">
<canvas id="kochsimpler_canvas" class="ac-canvas" height="400" width="600" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="kochsimpler_suffix" style="display:none">
</pre>
<pre id="kochsimpler_pre" class="active_out">
</pre>
<div id="kochsimpler_files" class="ac-files ac-files-hidden"></div>
</div>
<p>The final turn is 0 degrees — so it has no effect. But it has allowed us to
find a pattern and reduce seven lines of code to three, which will make
things easier for our next observations.</p>
<p>One way to think about this is to convince yourself that the function
works correctly when you call it for an order 0 fractal. Then do
a mental <em>leap of faith</em>, saying <em>“the fairy godmother</em> (or Python, if
you can think of Python as your fairy godmother) <em>knows how to
handle the recursive level 0 calls for me on lines 11, 13, 15, and 17, so
I don’t need to think about that detail!”</em> All I need to focus on
is how to draw an order 1 fractal <em>if I can assume the order 0 one is
already working.</em></p>
<p>You’re practicing <em>mental abstraction</em> — ignoring the subproblem
while you solve the big problem.</p>
<p>If this mode of thinking works (and you should practice it!), then take
it to the next level. Aha! now can I see that it will work when called
for order 2 <em>under the assumption that it is already working for level 1</em>.</p>
<p>And, in general, if I can assume the order n-1 case works, can I just
solve the level n problem?</p>
<p>Students of mathematics who have played with proofs of induction should
see some very strong similarities here.</p>
<p>Another way of trying to understand recursion is to get rid of it! If we
had separate functions to draw a level 3 fractal, a level 2 fractal, a level 1
fractal and a level 0 fractal, we could simplify the above code, quite mechanically,
to a situation where there was no longer any recursion, like this:</p>
<div id="kochnonrecurse" class="pywindow" >
<div id="kochnonrecurse_code_div" style="display: block">
<textarea rows="23" id="kochnonrecurse_code" class="active_code" prefixcode="undefined">
def koch_0(t, size):
t.forward(size)
def koch_1(t, size):
for angle in [60, -120, 60, 0]:
koch_0(t, size/3)
t.left(angle)
def koch_2(t, size):
for angle in [60, -120, 60, 0]:
koch_1(t, size/3)
t.left(angle)
def koch_3(t, size):
for angle in [60, -120, 60, 0]:
koch_2(t, size/3)
t.left(angle)
import turtle
wn = turtle.Screen()
t = turtle.Turtle()
koch(t, 3, 300)
wn.mainloop()</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['kochnonrecurse_code'] = true;
pythonTool.readOnlyFlags['kochnonrecurse_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="kochnonrecurse_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="kochnonrecurse_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="kochnonrecurse_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='kochnonrecurse_error'></div>
<div style="text-align: center">
<canvas id="kochnonrecurse_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="kochnonrecurse_suffix" style="display:none">
</pre>
<pre id="kochnonrecurse_pre" class="active_out">
</pre>
<div id="kochnonrecurse_files" class="ac-files ac-files-hidden"></div>
</div>
<p>This trick of “unrolling” the recursion gives us an operational view
of what happens. You can trace the program into <tt class="docutils literal"><span class="pre">koch_3</span></tt>, and from
there, into <tt class="docutils literal"><span class="pre">koch_2</span></tt>, and then into <tt class="docutils literal"><span class="pre">koch_1</span></tt>, etc., all the way down
the different layers of the recursion.</p>
<p>This might be a useful hint to build your understanding. The mental goal
is, however, to be able to do the abstraction!</p>
</div>
<div class="section" id="recursive-data-structures">
<span id="index-0"></span><h2>11.2. Recursive data structures<a class="headerlink" href="#recursive-data-structures" title="Permalink to this headline">¶</a></h2>
<p>All of the Python data types we have seen can be grouped inside lists and
tuples in a variety of ways. Lists and tuples can also be nested, providing
many possibilities for organizing data. The organization of data for the
purpose of making it easier to use is called a <strong>data structure</strong>.</p>
<p>It’s election time and we are helping to compute the votes as they come in.
Votes arriving from individual wards, precincts, municipalities, counties, and
states are sometimes reported as a sum total of votes and sometimes as a list
of subtotals of votes. After considering how best to store the tallies, we
decide to use a <em>nested number list</em>, which we define as follows:</p>
<p>A <em>nested number list</em> is a list whose elements are either:</p>
<ol class="loweralpha simple">
<li>numbers</li>
<li>nested number lists</li>
</ol>
<p>Notice that the term, <em>nested number list</em> is used in its own definition.
<strong>Recursive definitions</strong> like this are quite common in mathematics and
computer science. They provide a concise and powerful way to describe
<strong>recursive data structures</strong> that are partially composed of smaller and
simpler instances of themselves. The definition is not circular, since at some
point we will reach a list that does not have any lists as elements.</p>
<p>Now suppose our job is to write a function that will sum all of the values in a
nested number list. Python has a built-in function which finds the sum of a
sequence of numbers:</p>
<div id="sumworks" class="pywindow" >
<div id="sumworks_code_div" style="display: block">
<textarea rows="1" id="sumworks_code" class="active_code" prefixcode="undefined">
print(sum([1, 2, 8]))</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['sumworks_code'] = true;
pythonTool.readOnlyFlags['sumworks_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="sumworks_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="sumworks_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="sumworks_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='sumworks_error'></div>
<div style="text-align: center">
<canvas id="sumworks_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="sumworks_suffix" style="display:none">
</pre>
<pre id="sumworks_pre" class="active_out">
</pre>
<div id="sumworks_files" class="ac-files ac-files-hidden"></div>
</div>
<p>For our <em>nested number list</em>, however, <tt class="docutils literal"><span class="pre">sum</span></tt> will not work:</p>
<div id="sumdoesnotwork" class="pywindow" >
<div id="sumdoesnotwork_code_div" style="display: block">
<textarea rows="1" id="sumdoesnotwork_code" class="active_code" prefixcode="undefined">
print(sum([1, 2, [11, 13], 8]))</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['sumdoesnotwork_code'] = true;
pythonTool.readOnlyFlags['sumdoesnotwork_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="sumdoesnotwork_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="sumdoesnotwork_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="sumdoesnotwork_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='sumdoesnotwork_error'></div>
<div style="text-align: center">
<canvas id="sumdoesnotwork_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="sumdoesnotwork_suffix" style="display:none">
</pre>
<pre id="sumdoesnotwork_pre" class="active_out">
</pre>
<div id="sumdoesnotwork_files" class="ac-files ac-files-hidden"></div>
</div>
<p>The problem is that the third element of this list, <tt class="docutils literal"><span class="pre">[11,</span> <span class="pre">13]</span></tt>, is itself a
list, so it cannot just be added to <tt class="docutils literal"><span class="pre">1</span></tt>, <tt class="docutils literal"><span class="pre">2</span></tt>, and <tt class="docutils literal"><span class="pre">8</span></tt>.</p>
</div>
<div class="section" id="processing-recursive-number-lists">
<span id="index-1"></span><h2>11.3. Processing recursive number lists<a class="headerlink" href="#processing-recursive-number-lists" title="Permalink to this headline">¶</a></h2>
<p>To sum all the numbers in our recursive nested number list we need to traverse
the list, visiting each of the elements within its nested structure, adding any
numeric elements to our sum, and <em>recursively repeating the summing process</em> with any elements
which are themselves sub-lists.</p>
<p>Thanks to recursion, the Python code needed to sum the values of a nested number list is
surprisingly short:</p>
<div id="sumnestedlist" class="pywindow" >
<div id="sumnestedlist_code_div" style="display: block">
<textarea rows="11" id="sumnestedlist_code" class="active_code" prefixcode="undefined">
def r_sum(nested_num_list):
tot = 0
for element in nested_num_list:
if type(element) == type([]):
tot += r_sum(element)
else:
tot += element
return tot
print(r_sum([1, 2, [11, 13], 8]))
# should be 1+2+11+13+8 = 35</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['sumnestedlist_code'] = true;
pythonTool.readOnlyFlags['sumnestedlist_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="sumnestedlist_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="sumnestedlist_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="sumnestedlist_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='sumnestedlist_error'></div>
<div style="text-align: center">
<canvas id="sumnestedlist_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="sumnestedlist_suffix" style="display:none">
</pre>
<pre id="sumnestedlist_pre" class="active_out">
</pre>
<div id="sumnestedlist_files" class="ac-files ac-files-hidden"></div>
</div>
<p>The body of <tt class="docutils literal"><span class="pre">r_sum</span></tt> consists mainly of a <tt class="docutils literal"><span class="pre">for</span></tt> loop that traverses
<tt class="docutils literal"><span class="pre">nested_num_list</span></tt>. If <tt class="docutils literal"><span class="pre">element</span></tt> is a numerical value (the <tt class="docutils literal"><span class="pre">else</span></tt> branch),
it is simply added to <tt class="docutils literal"><span class="pre">tot</span></tt>. If <tt class="docutils literal"><span class="pre">element</span></tt> is a list, then <tt class="docutils literal"><span class="pre">r_sum</span></tt>
is called again, with the element as an argument. The statement inside the
function definition in which the function calls itself is known as the
<strong>recursive call</strong>.</p>
<p>The example above has a <strong>base case</strong> (on line 7) which does not lead to a
recursive call: the case where the element is not a (sub-) list. Without
a base case, you’ll have <strong>infinite recursion</strong>, and your program will not work.</p>
<p>Recursion is truly one of the most beautiful and elegant tools in computer
science.</p>
<p>A slightly more complicated problem is finding the largest value in our nested
number list:</p>
<div id="maxnestedlist" class="pywindow" >
<div id="maxnestedlist_code_div" style="display: block">
<textarea rows="24" id="maxnestedlist_code" class="active_code" prefixcode="undefined">
def r_max(nxs):
"""
Find the maximum in a recursive structure of lists
within other lists.
Precondition: No lists or sublists are empty.
"""
largest = None
first_time = True
for e in nxs:
if type(e) == type([]):
val = r_max(e)
else:
val = e
if first_time or val > largest:
largest = val
first_time = False
return largest
print(r_max([2, 9, [1, 13], 8, 6])) # should be 13
print(r_max([2, [[100, 7], 90], [1, 13], 8, 6])) # should be 100
print(r_max([[[13, 7], 90], 2, [1, 100], 8, 6])) # should be 100
print(r_max(["joe", ["sam", "ben"]])) # should be "sam"</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['maxnestedlist_code'] = true;
pythonTool.readOnlyFlags['maxnestedlist_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="maxnestedlist_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="maxnestedlist_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="maxnestedlist_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='maxnestedlist_error'></div>
<div style="text-align: center">
<canvas id="maxnestedlist_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="maxnestedlist_suffix" style="display:none">
</pre>
<pre id="maxnestedlist_pre" class="active_out">
</pre>
<div id="maxnestedlist_files" class="ac-files ac-files-hidden"></div>
</div>
<p>Tests are included to provide examples of <tt class="docutils literal"><span class="pre">r_max</span></tt> at work.</p>
<p>The added twist to this problem is finding a value for initializing
<tt class="docutils literal"><span class="pre">largest</span></tt>. We can’t just use <tt class="docutils literal"><span class="pre">nxs[0]</span></tt>, since that could be either
a element or a list. To solve this problem (at every recursive call)
we initialize a Boolean flag (at line 8). When we’ve found the value of interest,
(at line 15)
we check to see whether this is the initializing (first) value for
<tt class="docutils literal"><span class="pre">largest</span></tt>, or a value that could potentially change <tt class="docutils literal"><span class="pre">largest</span></tt>.</p>
<p>Again here we have a base case at line 13. If we don’t supply a base case,
Python stops after reaching a maximum recursion depth and returns a runtime
error. See how this happens, by running this little script which we will call <cite>infinite_recursion.py</cite>:</p>
<div id="infiniterecursion" class="pywindow" >
<div id="infiniterecursion_code_div" style="display: block">
<textarea rows="5" id="infiniterecursion_code" class="active_code" prefixcode="undefined">
def recursion_depth(number):
print(str(number), end=",")
recursion_depth(number + 1)
recursion_depth(0)</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['infiniterecursion_code'] = true;
pythonTool.readOnlyFlags['infiniterecursion_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="infiniterecursion_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="infiniterecursion_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="infiniterecursion_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='infiniterecursion_error'></div>
<div style="text-align: center">
<canvas id="infiniterecursion_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="infiniterecursion_suffix" style="display:none">
</pre>
<pre id="infiniterecursion_pre" class="active_out">
</pre>
<div id="infiniterecursion_files" class="ac-files ac-files-hidden"></div>
</div>
</div>
<div class="section" id="case-study-fibonacci-numbers">
<span id="index-2"></span><h2>11.4. Case study: Fibonacci numbers<a class="headerlink" href="#case-study-fibonacci-numbers" title="Permalink to this headline">¶</a></h2>
<p>The famous <strong>Fibonacci sequence</strong> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 134, ... was devised by
Fibonacci (1170-1250), who used this to model the breeding of (pairs) of rabbits.
If, in generation 7 you had 21 pairs in total, of which 13 were adults,
then next generation the adults will all have bred new children,
and the previous children will have grown up to become adults.
So in generation 8 you’ll have 13+21=34, of which 21 are adults.</p>
<p>This <em>model</em> to explain rabbit breeding made the simplifying assumption that rabbits never died.
Scientists often make (unrealistic) simplifying assumptions and restrictions
to make some headway with the problem.</p>
<p>If we number the terms of the sequence from 0, we can describe each term recursively
as the sum of the previous two terms:</p>
<div class="highlight-python"><div class="highlight"><pre>fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n >= 2
</pre></div>
</div>
<p>This translates very directly into some Python:</p>
<div id="fibrecurse" class="pywindow" >
<div id="fibrecurse_code_div" style="display: block">
<textarea rows="7" id="fibrecurse_code" class="active_code" prefixcode="undefined">
def fib(n):
if n <= 1:
return n
t = fib(n-1) + fib(n-2)
return t
print(fib(10)) # should print 55</textarea>
</div>
<script type="text/javascript">
pythonTool.lineNumberFlags['fibrecurse_code'] = true;
pythonTool.readOnlyFlags['fibrecurse_code'] = false;
</script>
<div>
<button style="float:left" type='button' class='btn btn-run' id="fibrecurse_runb">Run</button>
<button style="float:left; margin-left:150px;" type='button' class='btn' id="fibrecurse_popb">Pop Out</button>
<button style="float:right" type="button" class='btn btn-reset' id="fibrecurse_resetb">Reset</button>
<div style='clear:both'></div>
</div>
<div id='fibrecurse_error'></div>
<div style="text-align: center">
<canvas id="fibrecurse_canvas" class="ac-canvas" height="400" width="400" style="border-style: solid; display: none; text-align: center"></canvas>
</div>
<pre id="fibrecurse_suffix" style="display:none">
</pre>
<pre id="fibrecurse_pre" class="active_out">
</pre>
<div id="fibrecurse_files" class="ac-files ac-files-hidden"></div>
</div>
<p>This is a particularly inefficient algorithm. Change the 10 to 30 in line 7 of the code above and see how slowly it runs. Can you think of a faster way to implement this algorithm?</p>
</div>
<div class="section" id="glossary">
<h2>11.5. Glossary<a class="headerlink" href="#glossary" title="Permalink to this headline">¶</a></h2>
<dl class="glossary docutils">
<dt id="term-base-case">base case</dt>
<dd>A branch of the conditional statement in a recursive function that does
not give rise to further recursive calls.</dd>
<dt id="term-infinite-recursion">infinite recursion</dt>
<dd>A function that calls itself recursively without ever reaching any base
case. Eventually, infinite recursion causes a runtime error.</dd>
<dt id="term-recursion">recursion</dt>
<dd>The process of calling a function that is already executing.</dd>
<dt id="term-recursive-call">recursive call</dt>
<dd>The statement that calls an already executing function. Recursion can
also be indirect — function <cite>f</cite> can call <cite>g</cite> which calls <cite>h</cite>,
and <cite>h</cite> could make a call back to <cite>f</cite>.</dd>
<dt id="term-recursive-definition">recursive definition</dt>
<dd>A definition which defines something in terms of itself. To be useful
it must include <em>base cases</em> which are not recursive. In this way it
differs from a <em>circular definition</em>. Recursive definitions often
provide an elegant way to express complex data structures, like a directory
that can contain other directories, or a menu that can contain other menus.</dd>
</dl>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="classes.html" title="12. Classes and Objects — the Basics"
>next</a> |</li>
<li class="right" >
<a href="dictionaries.html" title="10. Dictionaries"
>previous</a> |</li>
<li><a href="index.html">How to Think Like a Computer Scientist: Learning with Python 3 (AoPS Edition)</a> »</li>
</ul>
</div>
<div class="footer">
© <a href="copyright.html">Copyright</a> 2014, AoPS Incorporated, 2012, Peter Wentworth, Jeffrey Elkner, Allen B. Downey and Chris Meyers.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.2.1.
</div>
</body>
</html>