Recursion¶

Taken from the book Think Python (2e):

http://greenteapress.com/wp/think-python-2e/

It is legal for one function to call another; 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 things a program can do. For example, look at the following function:

In [5]:
def countdown(n):
    #print(f"called with {n}")
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n-1)
        
countdown(8)

8
7
6
5
4
3
2
1
Blastoff!

A function that calls itself is recursive; the process of executing it is called recursion.

As another example, we can write a function that prints a string n times.

In [9]:
def print_n(s, n):
    if n <= 0:
        return
    print(s,end='')
    print_n(s, n-1)
    
print_n("abc ",10)

abc abc abc abc abc abc abc abc abc abc

by Ed:

Rercusive functions follow a pattern:

  • Return the function value immediately if the argument is simple enough. For example if a list argument is empty or a numeric argument has the desired final value (often zero or one).
  • Otherwise compute the return value as a function of one or more calls to the same function with simpler arguments. The simplification must ensure that the recursion will eventually terminate (e.g. call the function recursively with a shorter list or a smaller numeric argument).

It's often easier and clearer to define a recursive solution than to use loops and variables.

The the function can take multiple arguments or the argument passed to the function can contain multiple values.

If the recursive call is the last statement in the function ("tail call") then recursion may not require space on the stack and there is no limit to the number of recursive calls (true in some languages, but unfortunately not in Python). Otherwise the maximum call stack depth may limit the amount of recursion (e.g. to 1000 nested calls).

Recursion and Trees¶

Many types of problems can be defined as a graph with a tree structure.

To solve these problem we search through the tree for a node representing a solution (or often, the best solution).

Recursive algorithms are often used to search trees because each node can be the root of another tree. The recursive search algorithm is:

  • if a node is a solution, we terminate the search
  • otherwise, we search each possible tree rooted at that node.

The tree may be a static data structure such as nested lists in Python or linked lists in C. In other cases the branches from each node can be computed. In this case we only need to keep track of the state of each node in the path to the current node.