[Tutor] A small (but long) introduction to recursion
ak@silmarill.org
ak@silmarill.org
Wed, 25 Jul 2001 11:24:19 -0400
On Wed, Jul 25, 2001 at 10:06:19AM -0500, Kevin McCormick wrote:
> Danny Yoo wrote:
> >
> > I wrote this up today for a student in an introductory CS class; I thought
> > it might be interesting for people on tutor, so here's a version of the
> > introduction in Python.
> >
> > [warning: this is a somewhat long message.]
> >
> > ---
> >
> > Here's an example of a "recursive" problem: Let's say that we're trying
> > to add up the numbers:
> >
> > 0 + 1 + 2 + ... + n
> >
> > together. In Python, this is pretty easy:
> >
> > ###
> > ## non-recursive version of addUpToN
> > def addUpToN(n):
> > """Adds the numbers from zero to n, inclusive. 1 + 2 + ... + n"""
> > sum = 0
> > for i in range(n+1):
> > sum += i
> > return sum
> > ###
> >
> > And since it's so "easy" to define, let's make sure it works:
> >
> > ###
> > >>> addUpToN(0)
> > 0
> > >>> addUpToN(1)
> > 1
> > >>> addUpToN(2)
> > 3
> > >>> addUpToN(3)
> > 6
> > >>> addUpToN(10)
> > 55
> > >>> 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
> > 55
> > >>> reduce(lambda x, y: x + y, range(11)) # just playing around...
> > 55
> > ##
> >
> > Ok, it looks good. (Note: the first time I did this, I was off by a lot
> > by accidently doing "range(n)" instead of "range(n+1)". Testing code is a
> > very good idea. *grin*)
> >
> > However, there's a "recursive" way to view this problem, a way of
> > boomeranging the problem around itself: to add the numbers from 0 to n, we
> > can add the numbers from 0 to n-1. Once we have that, we can finish the
> > sum by adding 'n'. What we mean is that:
> >
> > ###
> > def addUpToNRecursive(n):
> > if n == 0: return 0
> > return addUpToNRecursive(n-1) + n
> > ###
> >
> > Let's test it out.
> >
> > ###
> > >>> addUpToNRecursive(0)
> > 0
> > >>> addUpToNRecursive(1)
> > 1
> > >>> addUpToNRecursive(2)
> > 3
> > >>> addUpToNRecursive(10)
> > 55
> > ###
> >
> > When we think about recursive solutions to problems, we try to figure out
> > a way of teasing out a smaller piece to help us out. The part that
> > actually does the brunt of the work is this line:
> >
> > return addUpToNRecursive(n-1) + n
> >
> > What we're telling Python is that: "To add (1 + 2 + 3 + .... + n), all we
> > need to do is add (1 + 2 + 3 + ... + n-1), and top it off with 'n'."
> > It's very neat and short. In technical terms, this is called the
> > "recursive step" --- the part that depends on a call to itself.
> >
> > The line right before, though,
> >
> > if n == 0: return 0
> >
> > seems a bit arbitrary, no? What happens if we pull it out?
> >
> > ###
> > def addUpToNBrokenRecursive(n):
> > return addUpToNBrokenRecursive(n-1) + n
> > ###
> >
> > The name gives a hint, but how is it "broken"? Let's try it out:
> >
> > ###
> > >>> addUpToNBrokenRecursive(0)
> > Traceback (most recent call last):
> > File "<stdin>", line 1, in ?
> > File "/usr/tmp/python-6609I5e", line 14, in addUpToNBrokenRecursive
> > File "/usr/tmp/python-6609I5e", line 14, in addUpToNBrokenRecursive
> > ... [lots and lots of lines later]
> > File "/usr/tmp/python-6609I5e", line 14, in addUpToNBrokenRecursive
> > RuntimeError: maximum recursion depth exceeded
> > ###
> >
> > Wow. This is akin to the "Are we there yet?" game that children use to
> > gleefully madden their parents.
> >
> > "Are we there yet?"
> > "No."
> > "Are we there yet?"
> > "No."
> > "Are we there yet?"
> > "No!"
> >
> > Unlike the road game, the road goes on and on in a recursion that doesn't
> > say when to stop. In addUpToNBrokenRecursive(),
> >
> > ###
> > def addUpToNBrokenRecursive(n):
> > return addUpToNBrokenRecursive(n-1) + n
> > ###
> >
> > what's missing is a "base case", something that the function is absolutely
> > sure it knows how to answer without calling itself. It needs a solid
> > foundation, and that's the role that the line,
> >
> > if n == 0: return 0
> >
> > plays. Of course, if we pass something like -1 off to the function, we'll
> > fall off the edge of the world again... But as long as we decide that
> > 'n' needs to be >= 0, that's ok.
> >
> > (Anyway, what does it even mean to do "0 + 1 + ... + -42"?)
> >
> > Anyway, better stop here. If you have any questions, feel free to email
> > the tutor list. If anyone requests it, we can show more examples of
> > recursion. Not everything molds well to a recursive solution, but in some
> > cases, it's a beautiful approach.
> >
> > Hope this helps!
> >
> > _______________________________________________
> > Tutor maillist - Tutor@python.org
> > http://mail.python.org/mailman/listinfo/tutor
>
> I absolutely do not understand recursion. I took your example and tried
> to do some tracing, but I do not understand how the sum is stored or
> returned:
>
> def addUpToNRecursive(n):
> if n == 0: return 0
> print n
> return addUpToNRecursive(n-1) + n
Picture it like this:
function is called, runs, and returns
addUpToNRecursive(10-1) + 10
then, from inside of return statement, function is called again, so you have
addUpToNRecursive(10-1) + 10
^^^^^^^^^^^^^^^^^^^^^^^
|
v
addUpToNRecursive(9-1) + 9
then again:
addUpToNRecursive(9-1) + 9
---------------------
|
v
addUpToNRecursive(8-1) + 8
[...]
until it reaches 0, at which point final value is ready and it looks like this:
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
I remember I had exactly the same problem, when I was studying C. My
misconception was that when the function calls itself from inside, that first
return statement is substituted by the new one instead of being added to it,
whereas in fact it indeed get added.
If your misconception is the same (or similar) maybe you'll benefit from me
spelling it out like that.. maybe not.
HTH,
- Andrei
>
> x = addUpToNRecursive(10)
> print x
>
> _______________________________________________
> Tutor maillist - Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
--
Cymbaline: intelligent learning mp3 player - python, linux, console.
get it at: http://silmarill.org/cymbaline