Recursion

Our next graph topic is the depth-first search algorithm that we have briefly introduced. The most natural way to write that algorithm is using a technique we haven't seen yet, called recursion. So, we're going to pause for a couple days to introduce this technique and explore its use.

What is recursion? Well, we've previously defined functions that called other functions. Recursion is the idea that we can define a function that calls itself. After all, if we can call, or use, any other function, why not the one we're defining? Some people find this idea simple and obvious, while others find it confusing.

Additionally, this idea leads to an additional way of breaking problems down into simpler ones. We can often solve a larger instance of a problem by breaking into down into one or more smaller instances of the same problem.

Interactive Examples

In class, we will interactively introduce and use various examples. After class, we will post the resulting code on the website.

Recursion vs. Iteration (i.e., Looping)

This subject is often discussed with religious intensity. We will bypass the fervor and summarize a few comparisons that will be made in class.

For many problems, such as those explored today, recursion and iteration are entirely comparable. These involve breaking a large problem into one smaller subproblem. In fact, we could describe a formal mathematical equivalence. But, in a more practical sense, the two approaches are of roughly equal simplicity, and which one is “better” is mostly a matter of personal preference and habit.

For some problems, such as those explored in the next class, recursion is a much simpler way to describe a solution. These involve breaking a large problem into two or more smaller subproblems.

Some programming languages encourage recursion more or less than others. This is generally because we used to lack the ability to implement functional calls and recursion particularly efficiently. Python generally discourages recursion in a variety of subtle ways, as a result of its designers' biases. One way is that it has a limit for the number of nested function calls you can make.

• import sys
  sys.getrecursionlimit()      # By default, the limit is 1000.
  
  sys.setrecursionlimit(5000)  # Or whatever limit.
      

Related Resources

• Khan Academy: Computer Science — See the factorial and Fibonacci examples