Introduction to Recursion

Many of the processes in nature are recursive. Imagine a process that starts with an equilateral triangle and replace the middle 1/3rd of each line segment by another equilateral triangle. If we continue this process again and again then the shape begin to show more like a snowflake. This is actually called a Koch snowflake

You can see a nice demonstration of this process at Wikipedia.

Computer language rules are defined recursively. For example, a language can specify the rule for defining a variable as follows.

 

 

 

 

 

 

 


alpha = {a,b,…,z};

var = alpha |  alpha {var}

 

This specifies that a variable in this language must be a finite combination of alpha characters.

 

Recursion is based on Mathematical notion of induction, where an inductive proof can be built by proving the theorem for n=1, then by showing in more general, that if an assumption that a theorem holds for n = r implies it holds for n = r+1, then theorem holds for all n.  The induction is a powerful mathematical tool for proving many interesting theorems. For example, we can prove that, for any n >= 1,

1 + 2 + …. + n = (n/2)(n+1)

We prove this by assuming if the case for (n-1) holds true then that implies that the case for n holds as well.

 

Definition

A process can be recursive in nature and a Formal Definition that defines a recursive function can be given as follows.

A function that calls itself directly (or indirectly) to solve a smaller version of its task until a final call which does not require a self-call is a recursive function.

In any recursive process it is important to have a terminal condition (which we call the base condition) to assure that the recursive process will end at some point. There are many examples of recursion that we encounter everyday. A computer file system can be recursively examined by looking at folders, sub-folders etc. In other words, to find all files in a directory, we look at its sub-folders, sub-folders of sub-folders etc. The process can terminate when there are no more sub-folders to look at. A pseudo algorithm/function that examines all files under a particular directory can be written as:

 

function list(dir D) {

   for all files in D

        list files

   for all folders Di in the D

        list(Di)

The important thing to understand about recursion is that, it is the same algorithm we keep applying until we find a base case or termination condition.  Recursion is a way to solve problems using a strategy call divide and conquer.

 

Divide and conquer approach is very common in programming. As we are dealing with large complex programs, it is always to better to think of a simple case first, then try to generalize it for more general cases. For example, if one is trying to solve a problem that involve n things, then it may be better to think how to solve the problem for n = 1. Often this is a trivial, but an important case. Now see if the solution to n = 2 problem can be obtained by using the solution to n = 1 case. We need to prove in general that we may be able to find the solution to n problem using the solution to n-1 problem. More strongly, we can find the solution to n problem using solutions to all the problems up to n-1. This is the basis for recursion.

 

Thinking Recursively

Let us start with a motivating example. Suppose you are given the task to find the least number of coins to give change for an amount less than 99 cents. A grocery clerk will probably do this without even thinking that he is applying a recursive algorithm in the process. Certainly our approach is to find the largest coin less than the amount and start with that coin. Once the largest coin is used we can look at the balance and apply the same algorithm to find the next largest coin less than the balance. Here is an example.

 

Assume we have to give change for 63 cents. So we do the following. In each step we choose the largest coin that is less than the balance. But the algorithm at each step is the same. Eventually, the balance goes to zero. Note that this may not work with all coin denominations. But it does work with US coins.

 

63 – 25 = 38 (1 coin)

38 – 25 = 13 (1 coin)

13 – 10 = 3 (1 coin)

3 – 1 = 2 (1 coin)

2 – 1 = 1 (1 coin)

1 – 1 = 0 (1 coin)

 

So we need 6 coins to give change. If we need to write this as a formal algorithm, we would say

 

numCoins(b) = 1 + numCoins(b-25)   if  b >= 25

numCoins(b) = 1 + numCoins(b-10)   if  25 > b >= 10

numCoins(b) = 1 + numCoins(b-5)   if  10 > b >= 5

numCoins(b) = 1 + numCoins(b-1)   if  5 > b >= 1

numCoins(0) = 0     { base case}

 

We note that solution to b problem can be found if we know the solution to b-25 etc.

 

Recursion is a powerful tool. Some algorithms required to solve complex problems can be recursive in nature. Recursive solutions are simple and elegant and mathematically sound.

 

Here is a recursive function that prints the digits of a number in decimal form.

 

public static void printDecimal(long n) {

     if (n > = 10)  printDecimal(n/10);

     System.out.print((char)(‘0’+(n%10)));

}

 

You can see the recursive nature of this Java function as it calls it-self during the process.

 

More Examples

You will encounter many problems in life that can be solved recursively. You need to have faith in your solution and that you can prove, if you can assume the solution to sub problem(s), then you can find the solution to the original problem. An interesting example of recursion is solving a Maze using recursion. Suppose you need to traverse a maze starting from one end and finding the exit from another end. It is computationally impossible to find all paths from beginning to the end. A pseudo algorithm for finding a recursive solution is as follows.

 

function MazeSolver(Maze M, currentCell){

     if (currentCell == destination)  return true;

     else { currentCell = visited;

               if (currentCell+1 is defined)  MazeSolver(M, currentCell + 1);

               if (currentCell-1 is defined)  MazeSolver(M, currentCell - 1);

               if (currentCell+M.numColumns is defined)  MazeSolver(M, currentCell + M.numColumns);

               if (currentCell-M.numColumns is defined)  MazeSolver(M, currentCell + M.numColumns);

           }

}            

 

Another interesting example of an elegant recursive solution is the Tower of Hanoi problem. In this problem, you are given 3 pegs, named origin, destination, and intermediate and n disks that are stacked from largest to the smallest. Your goal is to move all n disks from origin to destination using intermediate under the following assumptions. You can move only one disk at a time and you cannot place a larger disk on the top of a smaller disk. The problem seems simple enough to solve if the number of disks is small. For example, if n = 3, then we can easily find a solution that involves 7 steps. But for general n, the problem seems difficult to solve. Not so, if you are willing to look at the problem like this. Suppose you consider the following. You know how to solve or move (n-1) disks from origin to intermediate using destination. Then you move the largest disk (one that is called n) from origin to destination. Now you move the rest of the disks (n-1) from intermediate to destination using the origin. An implementation of this can be found in code examples.

 

 

 

Tail Recursion

Recursive calls can occur at any point of the algorithm. For example, if we consider a for loop, that runs from 0 to n-1, then we know that the loop body is executed repeatedly with different values of n. Similarly, If the recursive call occurs at the end of the function, called tail recursion, the result is similar to a loop. That is, function executes all the statements before recursive call before jumping into the next recursive call.

Example

public void foo(int n) {

     if (n == 1) return;

     else { System.out.println(n); foo(n-1);}

}

Question: What is the output if foo(5) is called?

Head Recursion

If the recursive call occurs at the beginning of the function, called head recursion, the function saves the state of the program before jumping into the next function call. That is, function waits to evaluate statements until the exit condition is reached. The state of the program is saved in a stack (we will learn more about stacks later in the course)

Example

void  foo(int n) {

    If  (n==0) return;

   else  { foo(n-1);

              System.out.println(n);

            }

}

Question: What is the output if foo(5) is called?