startsection section 1 0mm-3.5ex plus -1ex minus -.2ex0.7ex plus.2exRecursion

We mentioned that it is legal for one function to call another, and you have seen several examples of that. We neglected to mention that it is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do. For example, look at the following function:

def countdown(n):
  if n == 0:
    print "Blastoff!"
  else:
    print n
    countdown(n-1)

countdown expects the parameter, n, to be a positive integer. If n is 0, it outputs the word, ``Blastoff!'' Otherwise, it outputs n and then calls a function named countdown--itself--passing n-1 as an argument.

What happens if we call this function like this:

>>> countdown(3)

The execution of countdown begins with n=3, and since n is not 0, it outputs the value 3, and then calls itself...

The execution of countdown begins with n=2, and since n is not 0, it outputs the value 2, and then calls itself...

The execution of countdown begins with n=1, and since n is not 0, it outputs the value 1, and then calls itself...

The execution of countdown begins with n=0, and since n is 0, it outputs the word, ``Blastoff!'' and then returns.

The countdown that got n=1 returns.

The countdown that got n=2 returns.

The countdown that got n=3 returns.

And then you're back in __main__ (what a trip). So, the total output looks like this:

3
2
1
Blastoff!

As a second example, look again at the functions newLine and threeLines:

def newline():
  print

def threeLines():
  newLine()
  newLine()
  newLine()

Although these work, they would not be much help if we wanted to output 2 newlines, or 106. A better alternative would be this:

def nLines(n):
  if n > 0:
    print
    nLines(n-1)

This program is similar to countdown; as long as n is greater than 0, it outputs one newline and then calls itself to output n-1 additional newlines. Thus, the total number of newlines is 1 + (n - 1) which, if you do your algebra right, comes out to n.

The process of a function calling itself is recursion, and such functions are said to be recursive.