/
recursion.html
347 lines (278 loc) · 9.71 KB
/
recursion.html
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
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="chrome=1">
<title>Recursion: An Intuitive Explanation for Confused Beginners</title>
<link rel="stylesheet" href="stylesheets/styles.css">
<link rel="stylesheet" href="stylesheets/pygment_trac.css">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<!--[if lt IE 9]>
<script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
</head>
<body>
<div class="wrapper">
<header>
<h1>Recursion: An Intuitive Explanation for Confused Beginners</h1>
<p class="view"><a href="/">back to index</a></p>
</header>
<section>
<h2>What's wrong with recursion?</h2>
<p>The standard "computer science" treatment of recursive functions focuses on treating functions as their mathematical
equivalent. It is my impression that some students have problems understanding how recursion works.</p>
<p>I believe that this problem sometimes stems from a misunderstanding of how functions actually work in practice.
I hope that in addressing that misunderstanding, the behavior of recursion will also become clear.</p>
<p>Imperative programming is usually taught with <a href="https://en.wikipedia.org/wiki/Trace_table">trace tables</a>, such as:</p>
<pre><code>0: int x = 1;
1: for (int i = 0; i < 3; i++) {
2: x = x * 2;
3: }
</code></pre>
<table>
<thead>
<tr>
<th>line</th>
<th>x</th>
<th>i</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>1</td>
<td>-</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>2</td>
<td>2</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>4</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>4</td>
<td>2</td>
</tr>
<tr>
<td>2</td>
<td>8</td>
<td>2</td>
</tr>
<tr>
<td>1</td>
<td>8</td>
<td>3</td>
</tr>
<tr>
<td>3</td>
<td>8</td>
<td>3</td>
</tr>
</tbody>
</table>
<p>However, this carries a grave risk.</p>
<p>Teaching variables in this way makes it seem like there is a single "blank form" with one field for every
variable, into which values are written and rewritten.</p>
<p>This is <strong>false</strong>. It works for simple programs, but it <strong>completely</strong> fails to explain recursion - more than that, it is actively
harmful to its understanding.</p>
<h2>the actual truth</h2>
<p>If we are to keep the analogy of a "blank form," the <em>correct</em> way to consider a function is as a "master template".</p>
<p>A better analogy: instead of a bunch of forms loosely laid on a table, what we are actually working with is a <strong>stack</strong>
of forms, of which only the top is visible. Whenever we call a function, we take that function's form, which is described by the code,
and run a <em>copy</em> of it, which we place on top of the stack, filling in its parameter fields with the values given to the function.
When we return from the function, we simply remove the top sheet and write in its final return value for the call.</p>
<h2>an example</h2>
<p>Take the Fibonacci function, the archetypal example of recursion.</p>
<pre><code>0: function fib(n)
1: if n = 1
2: then return 1
3: else if n = 2
4: then return 1
5: else return fib(n - 1) + fib(n - 2)
6: print fib(5)
</code></pre>
<p>If we attempt to look at this function the way we have previously considered simple code, with a trace table, we get hopelessly confused:</p>
<table>
<thead>
<tr>
<th>line</th>
<th>n</th>
</tr>
</thead>
<tbody>
<tr>
<td>6</td>
<td>-</td>
</tr>
<tr>
<td>0</td>
<td>5</td>
</tr>
<tr>
<td>1</td>
<td>5</td>
</tr>
<tr>
<td>3</td>
<td>5</td>
</tr>
<tr>
<td>5</td>
<td>5</td>
</tr>
<tr>
<td>0</td>
<td>4 wait what?</td>
</tr>
</tbody>
</table>
<p>What is actually happening here?</p>
<p>"fib" is not a form with a field "n": it is a "master form", of which we run a copy every time we encounter a call.</p>
<p>If we look at our stack of forms, this is what actually occurs:</p>
<table>
<thead>
<tr>
<th>line</th>
<th>stack</th>
</tr>
</thead>
<tbody>
<tr>
<td>6</td>
<td>-</td>
</tr>
<tr>
<td>0</td>
<td>[n = 5]</td>
</tr>
<tr>
<td>1</td>
<td>[n = 5]</td>
</tr>
<tr>
<td>3</td>
<td>[n = 5]</td>
</tr>
<tr>
<td>5</td>
<td>[n = 5]</td>
</tr>
<tr>
<td>0</td>
<td>[n = 5] [n = 4]</td>
</tr>
</tbody>
</table>
<p>Do you see? There is not just one variable <code>n</code>; there are actually <em>many</em> - one for each time we call the function.</p>
<p>We can imagine that any time we return a value from fib, we take the field on the current top form labelled "return value", cut it out,
and paste it over that call in the form <em>beneath</em> it.</p>
<pre><code># template:
function fib(n)
...
# we do a call
print fib(5)
# which means we take a copy of the form for fib,
# and pencil in its value of n with 5
function fib(5)
if 5 = 1 ...
else if 5 = 2 ...
else return fib(5 - 1) + fib(5 - 2)
# we hit a further call to fib(4), which means
# we take a copy of the *original* form for fib
# and pencil in its value of n with 4
# NEW FORM
function fib(4)
if 4 = 1 ...
else if 4 = 2 ...
else return fib(4 - 1) + fib(4 - 2)
# NEW FORM
function fib(3)
if 3 = 1 ...
else if 3 = 2 ...
else return fib(3 - 1) + fib(3 - 2)
# NEW FORM
function fib(2)
if 2 = 1 ...
else if 2 = 2 return 1
</code></pre>
<p>At this point, our stack of forms looks like this, from top to bottom:</p>
<ul>
<li>fib(2) - current top form</li>
<li>fib(3)</li>
<li>fib(4)</li>
<li>fib(5) - our initial form</li>
</ul>
<p>So we actually have four versions of the variable <code>n</code> hanging around.</p>
<p>Note: In programming, this is known as the "call stack", and each form sheet is called a "stack frame".</p>
<p>Now, we've hit a "return" statement in <code>fib(2)</code>. What does this mean?</p>
<p>First, we remove the <code>fib(2)</code> sheet from the stack, bringing <code>fib(3)</code> back to the top.</p>
<p>Then we simply pencil in the return value for fib(2), 1, <em>on that sheet</em>.</p>
<pre><code>function fib(3)
...
else return 1 + fib(3 - 2)
</code></pre>
<p>and proceed to the next part of the code.</p>
<pre><code># NEW FORM
function fib(1)
if (1 = 1) return 1
</code></pre>
<p>Our stack now looks like: <code>fib(5)</code>, <code>fib(4)</code>, <code>fib(3)</code>, <code>fib(1)</code></p>
<p>Take the sheet off, revealing <code>fib(3)</code> again:</p>
<pre><code>function fib(3)
...
else return 1 + 1
</code></pre>
<p>And so we remove <code>fib(3)</code> from the stack, revealing <code>fib(4)</code> and filling in its call to <code>fib(4 - 1)</code> with 2. And so on,
until the very last sheet is removed, and the program runs to completion and halts.</p>
<h1>What have we learnt?</h1>
<p>To sum it up: when you are looking at a variable in a function, this is not actually a place that holds a value;
rather, there is one version of this variable for every time the function is called, with the most recent version "on top".</p>
<h1>Why go through all this effort?</h1>
<p>So that recursion works. That's pretty much the only reason.</p>
<p>In old programming languages, functions worked like one would initially think, with every variable only existing once and having
a single value at a time. In these days, keeping a call stack would have been a nontrivial expense - you can read up on
the historical development of recursion
<a href="https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/">in this excellent blogpost</a>.</p>
<p>As computers have gained more memory, this tradeoff has largely become irrelevant. Every modern language now keeps a call stack.</p>
<h1>a more advanced topic: call and return in detail</h1>
<p>How does all this "calling" and "returning" actually work at the hardware level?</p>
<p>It is not very incorrect to say that as the computer executes the program, it runs a finger along the code, executing it as it goes.
When it hits a call to a function, it has to move its finger (the "instruction pointer") over to the top of that function (and make a
new form ("stackframe"), and fill in its parameters).</p>
<p>This works fine, until you have to hit a "return" statement, at which point we discard the form and go back to where we came from.</p>
<p>But how does the computer actually know where to return to?</p>
<p><em>It simply uses the call stack</em>.</p>
<p>Every time the processor prepares a new form, it puts a field at the very top, labelled 'where I came from'. When we hit a return
statement, and the computer removes the top sheet, it just has to look at this field to remind itself where to go back to.</p>
<p>A historical note: in the very early days, before the invention of the stack, we used to write code in terms of direct jumps - literally
telling the computer "continue the execution over there". Everyone knows the classic example:</p>
<pre><code>10 PRINT "HELLO, WORLD"
20 GOTO 10
</code></pre>
<p>This may seem simple, but it has a crippling flaw: you have to keep track of where to keep going in <em>every</em> part of the code.</p>
<p>The invention of the notion of a return address is what allowed us to write code that could work the same way no matter
where we called it from. It allows us to break up our problems into smaller sub-tasks, that can be reused in all sorts
of different places, and it integrates with the call stack in a very natural way.</p>
</section>
<footer>
<p><small>Hosted on GitHub Pages — Theme by <a href="https://github.com/orderedlist">orderedlist</a></small></p>
</footer>
</div>
<script src="javascripts/scale.fix.js"></script>
</body>
</html>