Recursion is a technique to solve a problem by solving one or more sub-states (or previous states) of the problem itself. When a problem has the patterns like “compute the nth ….” or “list the first n ….”, it is often a good candidate for recursion.

Generally, there are two patterns of recursions: bottom-up recursion and top-down recursion.

Bottom-Up Recursion

Bottom-up recursion is very intutive. For a problem of f(n), we start solving it by knowing the result of f(1) and figuring out how to solve f(2), then f(3) and so on. Eventually we could get the result of f(n). The key here is to think about how to build the solution for one case from the result of the previous case. Often in a bottom-up recursion solution, there is only one call to the previous case f(k) where k is less than n.

Here is a very simple example of bottom-up recursion. Caculate sum(n) = 1 + 2 + 3 + …. + n where n is greater than or equal to 1. Obiviously we know the result of sum(1) = 1, and with sum(1), sum(2) = sum(1) + 2, and in the end, f(n) = f(n-1) + n. Here is the sample code for the problem.

int sum(int n){
  if(n==1) return 1;
  return sum(n-1) + 1;
}

Top-Down Recursion

Top-down recursion often divides a problem into multiple sub-problems. This means that for a problem of f(n), it can be divided into some sub-problems. The key difference to bottom-up recursion here is that, very often, we need the results of more than one sub-problems, f(n-1), f(n-2), etc, to get the result of f(n).

Here is a simple example of top-down recursion. Imagine that you’re asked to implement the Fibonacci Number f(n) where f(0)=0, f(1)=1, and f(n) = f(n-1) + f(n-2). Here is the sample solution code.

int fibonacci(int n){
  if(n == 0) return 0;
  if(n == 1) return 1;

  return fibonacci(n-1)
        +fibonacci(n-2);
}

/* Note that the solution 
is not a performance optimized 
solution. A more efficient solution 
is given in the Dynamic Programming 
post.
*/

Here, we divided a problem, fibonacci(n) to two sub-problems, fibonacci(n-1) and fibonacci(n-2).

RelatedPost