forked from ninas/umonya_notes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrecursion.html
More file actions
181 lines (144 loc) · 6.73 KB
/
recursion.html
File metadata and controls
181 lines (144 loc) · 6.73 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
<!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>
<title>Introductory Programming in Python: Recursion</title>
<link rel='stylesheet' type='text/css' href='style.css' />
<meta http-equiv='Content-Type' content='text/html; charset=utf-8' />
<script src="animation.js" type="text/javascript">
</script>
</head>
<body onload="animate_loop()">
<div class="page">
<h1>Introductory Programming in Python: Lesson 27<br />
Recursion</h1>
<div class="centered">
[<a href="debugging.html">Prev: Debugging</a>] [<a href="index.html">Course Outline</a>] [<a href="classes.html">Next: Classes and Objects</a>]
</div>
<h2>What is Recursion?</h2>
<p>Recursion is a general technique for tackling large problems. It
works by identifying problems that are larger cases of the same
problem, and how to solve the larger case in terms of the smaller case.
The smallest case of the problem is usually trivial to solve. More
formally, we define a recursion as any definition (function, or data
structure) that is defined in terms of itself.</p>
<p>Think of a branch on a tree. We could say that a branch is a
straightish piece of wood, from which various smaller branches extend.
Note the fact that in defining a branch, we've used the term 'branch'.
We have defined branch in terms of itself. Of crucial importance though
is that we've defined branch in terms of smaller instances of itself.
Ultimately we'll get to the point where the branch becomes a twig (i.e.
a very small branch) which has no branches extending from it.</p>
<blockquote class='problem'>
How many ways are there to arrange six marbles of six different
colours in a line?
</blockquote>
<p>A simple question? Perhaps! Let's approach it in the programming
way. Break it down into smaller problems. How many ways are there to
arrange one marble? One. Two marbles? Two. Three marbles? Three? No! If
we have red, green, and blue marbles, we can order them like so: RGB,
RBG, GRB, GBR, BRG, and BGR. That's six ways. We work this out
mathematically as follows; How many colours can go in the first
position? 3. Given the fact that one marble has been removed from the
choice, how many choices of colour do we have for the second position?
2. That yields six choices so far (3 times 2). There is only one marble
for the final position; it's colour is already determined by the
previous two choices, so we multiply simply by 1.</p>
<p>So what we've done is we've taken three positions <code>_ _ _</code>
and filled them up with their respective number of choices, <code>3 2
1</code> and multiplied the whole lot. Now let's write a python
function to calculate the number of choices for one marble, the
simplest case.</p>
<pre class='listing'>
#A function to calculate how many possible ways there are to order
#n marbles of different colours.
def numorders():
return 1
</pre>
<p>Easy, but what about 2 marbles? Well we know that we need to
multiply the number of choices in the first position by the number of
choices in the second position, so we get</p>
<pre class='listing'>
#A function to calculate how many possible ways there are to order
#n marbles of different colours.
def numorders(num_marbles):
if num_marbles == 2:
return 2*1
else:
return 1
</pre>
<p>Still simple, let's go to three.</p>
<pre class='listing'>
#A function to calculate how many possible ways there are to order
#n marbles of different colours.
def numorders(num_marbles):
if num_marbles == 3:
return 3*2*1
if num_marbles == 2:
return 2*1
else:
return 1
</pre>
<p>Alright, this is already getting tedious, time to get lazy-smart. If
we look at the condition for 3 when we call <code>numorders(3)</code>,
we get <code>3*<strong>2*1</strong></code>. But <code>2*1</code> is
what we get when we call <code>numorders(2)</code>. Similarly
<code>2*1</code> could be rewritten <code>2*numorders(1)</code>, so why
not do the following</p>
<pre class='listing'>
#A function to calculate how many possible ways there are to order
#n marbles of different colours.
def numorders(num_marbles):
if num_marbles == 3:
return 3*numorders(2)
if num_marbles == 2:
return 2*numorders(1)
else:
return 1
</pre>
<p>Now suppose we want to extend our function to deal with many
marbles. If 'n' is the number of marbles, we already notice the pattern
that <code>numorders(n)</code> can be written as
<code>n*numorders(n-1)</code>. Except in the case of 1.
<code>numorders(1)</code> simply returns one.</p>
<pre class='listing'>
#A function to calculate how many possible ways there are to order
#n marbles of different colours.
def numorders(num_marbles):
if num_marbles > 1:
return n*numorders(n-1)
else:
return 1
</pre>
<p>There is in fact a name for this function in mathematics. It is
known as the factorial, and represented using '!', as in the factorial
of n is written as 'n!'.</p>
<h2>The Simplest Case</h2>
<p>Now that we've got our heads around our first recursion, let's look
at recursion somewhat analytically. Every recursion contains two parts.
The first is the simplest case. This is something that is directly
solvable without referring to smaller cases of the same problem. In our
factorial example, it was the case of 1. The factorial of one is one,
essentially by definition. If a recursion does not have this simplest
case, it will never stop. We will get what is known as an infinite
recursion. As the simplest case is exactly that, simple, it is often
easiest to establish the simplest case first, and work out how to solve
it. This gives the ideal platform for the next task.</p>
<h2>A Smaller Case of The Same Problem</h2>
<p>Once we have the simple case worked out, we wish to express the next
most simple case in terms of the simple one, generally. This is the
core of recursion. The expression of a problem in terms of it's
parameters, and the same problem with smaller or simpler
parameters.</p>
<img src='images/recursion-formal-def.png' alt='Equation' />
<img src='images/factorial-eg.png' alt='Factorial Walkthrough' />
<h2>Exercises</h2>
<div class="centered">
[<a href="debugging.html">Prev: Debugging</a>] [<a href="index.html">Course Outline</a>] [<a href="classes.html">Next: Classes and Objects</a>]
</div>
</div>
<div class="pagefooter">
Copyright © James Dominy 2007-2008; Released under the <a href="http://www.gnu.org/copyleft/fdl.html">GNU Free Documentation License</a><br />
<a href="intropython.tar.gz">Download the tarball</a>
</div>
</body>
</html>