GOTO Table of Contents

Recursion is often a feared and dreaded word among new computer scientists. Most see it as a mystical process that they have no hope of understanding. Others loudly proclaim that they’ve been programming for years and have never needed recursion, mostly because they see it as a mystical process that they have no hope of understanding.

However recursion is actually pretty straightforward. And that’s a good thing, because there are a lot of problems that have very elegant recursive solutions. We’ll cover some of those when we learn about tree algorithms and sorting in future WITH articles.

For now we’re going to focus on the basics of recursion. Recursive functions are most often used as a form of loop and for this article we’ll use one of the most basic loops; counting. We’re going to describe a process of printing all the numbers from 0 to infinity. Without recursion you would probably write something similar to the following.

def count(n):
  while 1:
    print n
    n = n + 1

count(0)
0
1
2
...

Next we’ll look at the recursive solution.

def count(n):
  print n
  count(n+1)

count(0)
0
1
2
...
998
RuntimeError: maximum recursion depth exceeded

The above code should be pretty self-explanatory, but I’ll explain it a little bit anyway. The function count has only two instructions. First print n to the screen, then call count with n + 1 as the argument. So when we call count(0) it should print 0 then call count(1) which will print 1 then call count(2)…

You probably noticed the error in the above output. We’re going to ignore that for the moment and move on from trying to count to infinity. Let’s just count to 5. To tell when we’ve hit 5 we’ll need to check the value of n each time count is called.

def count(n):
  if n < 5:
    print n
    count(n+1)

count(5)
0
1
2
3
4

As you can see from these examples, a recursive function is simply a function that calls itself. Let’s look at another recursive solution to counting. This time we’re going to use a list of the numbers 0 through 4 and print each number in the list.

def print_list(lst):
  if lst:
    print lst[0]
    print_list([1:])

print_list(range(5))
0
1
2
3
4

In this code we print the first element in the list, then call print_list with the rest of that list from the 2nd element on. Here’s a diagram of the process to make it a bit more clear.

When writing recursive code it is important to include a stopping condition, which was the empty list in the code above. If you don’t include a stopping condition, your code will enter an infinite loop.

Tail-Call Optimization

One problem with recursive code is that most programming languages translate recursive code into something very similar to the diagram above.

Let’s go back to trying to print to infinity again and look at the error when we run the code. Depending on how many lines your terminal logs you may not see this.

993
994
995
996
997
998
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  ...
  RuntimeError: maximum recursion depth exceeded

Since most languages, Python included, see recursive code exactly like the diagram above, try to imagine how big our diagram would have to be to represent a 1,000! Eventually the language simply runs out of memory to store this huge diagram or it hits a set limit to prevent that from happening.

Let’s take a look at another example, countdown. This function simply counts down from a number, n to 1.

def countdown(n):
  if n:
    print n
    countdown(n-1)

countdown(5)
5
4
3
2
1

Each time Python sees countdown(n-1) it makes a new function call. Because Python is lexically scoped, the function call creates a new frame to hold the bindings and arguments. When the next countdown(n-1) is evaluated a new frame is created inside the last frame. Then again, and again, until it looks like the code below, each new level of indentation is a new frame within the previous frame.

countdown(5)
  print 5
  countdown(4)
    print 4
    countdown(3)
      print 3
      countdown(2)
        print 2
        countdown(1)
          print 1
          countdown(0)

From looking at the code above, it doesn’t make much sense why any language would do this. However if you switch the code for countdown around a little bit, it starts to make sense.

def countdown(n):
  if n:
    countdown(n-1)
    print n

All we did was switch the countdown and print lines, but let’s see how that changes the execution of this function.

countdown(5)
1
2
3
4
5

This version of countdown doesn’t countdown at all! In fact it counts up. To see why, let’s examine the execution of this function.

countdown(5)
  countdown(4)
    countdown(3)
      countdown(2)
        countdown(1)
          countdown(0)
          print 1
        print 2
      print 3
    print 4
  print 5

And a longer, but more descriptive version…

countdown(5)
  if 5:
    countdown(5 - 1)
      if 4:
        countdown(4 - 1)
          if 3:
            countdown(3 - 1)
              if 2:
                countdown(2 - 1)
                  if 1:
                    countdown(1 - 1)
                    print 1
                print 2
            print 3
        print 4
    print 5

In this scenario there is a print instruction after the call to countdown. This means that the language must evaluate countdown before printing the number. The only way to do this is to create a tree structure as depicted above and keep it all in memory until the function has finished executing.

Some languages like Scheme perform tail-call optimization (TCO), also known as tail-call elimination. If the recursive function call is the last thing you do in the function body, there cannot be anymore instructions to perform after the call. Because it is guaranteed that none of the information from the initial frame is needed, there is no reason to keep it around by nesting new frames in it. In other words tail-call optimization transforms a recursive definition into an iterative one.

Language support for tail-call optimization varies widely. Some languages, like Scheme, guarantee that recursive function calls in the tail position will run in constant space. While on the lower end of the spectrum is a compiler like gcc that may run tail calls in constant space, even though the C standard does not support TCO.

Languages that guarantee tail-call optimization generally use recursion as the main form of looping. Because of this function calls in these languages are usually highly optimized.

Here are tail-call optimized versions of count and countdown in Scheme. Notice how the recursive calls are the last calls that are executed in the body.

(define (count n)
  (print n)
  (count (+ n 1)))

(define (countdown n)
  (if (= n 0)
    (print n)
    (begin
      (print n)
      (countdown (- n 1)))))

(countdown 3)
3
2
1
0
(count 0)
1
2
3
...

Mutually Recursive Functions

This is the classic example of a mutually recursive function. These two functions together will determine whether a number is even or odd. Take a minute to look at the code and try to figure out for yourself how it works.

def even(n):
  if n == 0:
    return True
  else:
    return odd(n-1)

def odd(n):
  if n == 0:
    return False
  else:
    return even(n-1)

even(4)
#===> True
odd(4)
#===> False
odd(3)
#===> True

Because everyone likes a good sports analogy let’s imagine two kids playing catch. One kid is named Even and the other is named Odd. Even starts with the ball in his hand and they throw the ball back and forth until they lose count. If Even has the ball last, they threw the ball an even number of times. If Odd has the ball last, they threw the ball an odd number of times. When they finish playing, the kid with the ball screams “I got it!” and the game ends.

The mutually recursive function above works the same way. even subtracts 1 from the number and throws it to odd. odd also subtracts 1 from the number and throws it back to even. When the number reaches 0 the last function to have the number returns, #t if even is the last to have it and #f if odd is the last to have it.

We’ve already learned that a recursive function creates a loop by calling itself. Mutually recursive functions create a loop by calling each other. Like recursive functions, mutually recursive functions must check for some condition to prevent an infinite loop.

GOTO Table of Contents