Category:Recursion

Recursion is the idea that a function can come to an answer by repeatedly calling itself with new arguments until a "base case" or "end condition" is met. One good example is a factorial function. The base case for factorial is "0!" (some people like to use 1 or 2, but 0 is OK for instructional purposes). When 5 is sent as an argument to a recursive factorial function, the function does not know the answer right away. All it knows is that 5! = 5 * 4!. So it calls itself to find out what 4! is. This process continues until it gets to 0!, which is 1. Now it has built up a train of answers: 5! = 5 * 4! = 5 * 4 * 3! etc., and it can find the final answer. Other common examples include tree traversal and the min/max algorithm.

A pseudocode function to demonstrate recursion would look something like this:

function F with arguments
    if end condition is not met
      return F called with new set of arguments
    else
      return end condition value

More than one end condition is allowed. More than one recursion condition is allowed.

Many recursion problems can be solved with an iterative method, or using a loop of some sort (usually recursion and iteration are contrasted in programming, even though recursion is a specific type of iteration). In some languages, the factorial example is best done with a loop because of function call overhead. Some other languages, like Scheme, are designed to favor recursion over explicit looping, using tail recursion optimization to convert recursive calls into loop structures. If loop structures are not available (or not allowed) in your language, recursion is a good way to go.

Below is a list of examples of recursion in computing.