Week 11: Recursion

Recursion

Any function that sometimes calls itself is known as a recursive function. In most cases, recursion can be considered an alternative to iteration (loops). Instead of defining a loop structure, recursion defines a problem as a smaller problem until it reaches an end point. There are three requirements for a successful recursive function:

  1. Base case: each function must have one or more base cases where the function does not make a recursive call to itself. Instead, the problem has reached its smallest point, and we can begin returning back the small solutions.

  2. Recursive case: the function makes one (or more) calls to itself. The call must use a different argument to the function (or else we keep making the same recursive call over and over again!). Typically, the problem gets 1 smaller.

  3. All possible recursive calls must be guaranteed to hit a base case. If you miss one, your program is susceptible to an infinite recursion bug!

Example: Print a Message

The printmessage.py program prints a given message n times. We’ve already seen how to solve this problem with a loop (this is known as an iterative solution, one that uses a loop to repeat). However, let’s explore how we can solve it without a loop using recursion.

To think about how to define printing a message n times in a recursive way, we want to define printing in terms of printing. In other words we want to think of a recursive definition of printing n things, and our recursive function’s structure will follow this with it recursive function calls:

print_message(msg, num_times) is equivalent to:

  1. print(msg)
  2. print_message(msg, num_times-1)  # here is our recursive definition

To understand what’s happening with recursion, it’s often helpful to draw a stack diagram. The key concept is that Python treats the recursive function call the same as any other function call — it places a new stack frame on top and begins executing the new function. The only difference is the function in this case has the same name.

Examples with slicing

When developing recursive solutions, it helps to think about how to solve a big problem by

  1. solving a smaller problem of the exact same form (the recursive part)

  2. doing a small amount of work (combining the recursive result with a little extra info)

Many functions on lists can be solved recursively. We can break a large list into smaller pieces using slicing. In length_sol.py and max_sol.py, we use slicing to make a smaller list. We solve the problem recursively on the smaller list and combine the recursive solution with a litte bit of extra work to solve the original, bigger problem.