[Tutor] A small (but long) introduction to recursion

[Kevin McCormick]

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

x = addUpToNRecursive(10)
print x