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

[Danny Yoo]

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!