Revising Recursion

I was going to write about Backtracking this time. But then I thought that it would be better to post about recursion first as it is a very important weapon. Algorithms such as Backtracking, Depth First Search, Disjoint Set Union (also known as Union Find), Segment trees and many other graph algorithms are best implemented using recursion.

Recursion is when a problem is defined in terms of smaller instances of the same problem. A very well known example is the factorial of a number. We can define factorial of a number in two ways.
First is the iterative way,
factorial(n)= product(i=1 to n) ( i )

The second way is the recursive way,
factorial(n)=n*factorial(n-1) .

Of course, both the definitions lead to the same values. In the recursive definition, the factorial of n is shown in terms of factorial of (n-1) (i.e. in terms of a smaller factorial problem).

Programs implemented using recursion can be incredibly short and at the same time incredibly difficult to understand. So it’s essential that some properties of recursion are understood properly before starting the algorithms I mentioned in the start of my post.

Let’s look at the code for factorial of a positive number, n. The code is pretty straight forward.

long long factorial(long long n)
{
  if(n==0)
    return 1;
  long long a=factorial(n-1);
  return n*a;
}

A recursive function is one that can call itself.

When a function is called, we say that an instance of that function is created.

Here, factorial() is a recursive function. Note that, it has a call to itself in its body. factorial() is capable of calling itself, and the call at line 5 is called a recursive call.

When a function calls itself, a different instance of that function is created whose variables are completely different than the calling function. Eg. if I want to find 4!, I will call factorial(4). factorial(4) will in turn call factorial(3). The variables ‘n’ and ‘a’ are different for both these instances of factorial(), i.e. the variables have different locations in memory and store different values. For the first one n=4 and for the second one n=3.

All instances of factorial() will execute completely independent of each other. One instance of factorial doesn’t care about the value of ‘n’ or any other variable in other instances of factorial().

For an instance of a recursive function to terminate, all its child instances should first terminate. Eg. For factorial(4) to terminate, first its child instance i.e. factorial(3) should terminate.

recursion_factorial

Recursion depth:

An instance of a recursive function is said to be at depth d, if there are d instances of that function present above it.
In the previous example, factorial(4) is at depth 0, factorial(3) is at depth 1, factorial(2) is at depth 2, factorial(1) is at depth 3 and factorial(0) is at depth 4.

Consider the following code snippet:

void func(int depth)
{
  if(depth==10)
  {
    printf("reached depth of %d, now returning back",depth);
      return;
  }
  printf("at depth %d\n",depth);
  func(depth+1);
  printf("returning from depth of %d\n",depth);
}
int main()
{
  func(0);
  return 0;
}

In this code, we are limiting the maximum depth to which func() can be recursively called to 10.
Keep in mind that each instance of func() has different ‘int depth’ variable.
Notice how we are passing an incremented value of depth in the recursive function call func(depth+1).
This is a very common technique to increment values while calling recursively.

An infinite recursion is also possible which is just like an infinite loop. Suppose I forgot to increment the depth while passing it:

void func(int depth)
{
  if(depth==10)
  {
    printf("reached depth of %d, now returning back",depth);
      return;
  }
  printf("at depth %d\n",depth);
  func(depth);//notice the lack of +1 here
  printf("returning from depth of %d\n",depth);
}
int main()
{
  func(0);
  return 0;
}

This code will run until eternity as the condition that ends the recursion is never met.
Okay, so this covers the basic terminology and few techniques.

As an advanced example, lets write a program to find all length n permutations of the digits 1,2,3 using recursion.

int permutationcount=0;
void permute(int atdepth, int n, int selections[])
{
  if(atdepth==n)
  {
    int i;
    printf(“Permutation %d: “,permutationcount);
    for(i=0;i<n;i++)
      printf(“%d “,selections[i]);
    printf(“\n”);
    permutationcount++;
    return;
  }
  selections[atdepth]=1;
  permute(atdepth+1,n,selections); // select 1 for current position
  selections[atdepth]=2;
  permute(atdepth+1,n,selections); // select 2 for current position
  selections[atdepth]=3;
  permute(atdepth+1,n,selections); // select 3 for current position
  return;
}
int main()
{
  int a[1000],n;
  scanf(" %d",&n);
  permute(0,n,a);
  return 0;
}

See the following image to understand the order of function calls:
recursion_permute

A few important observations:
1. An instance of the recursive function permute() at depth d sets the value of selections[d], i.e. the (d+1)th position in the final permutation. And then calls permute() again to compute the rest of the permutation.
2. Each instance of permute() contains three recursive calls within it. Each one represents a different selection of number for the current position.
3. When a depth of n is reached, n numbers have been set in the selections[] array. And the array is printed.
4. A recursion depth of n is reached 3^n times. Because there are 3^n permutations possible.
5. Global variables are preserved among all the recursive instances of permute(). The variable permutationcount is used to keep track of the number of permutations.

For a particular instance of permute(), the call at line 17 will be executed only when the call at line 15 (along with all the subsequent calls that arise from inside it) complete execution.
And the call at line 19 will be executed only when the calls at lines 15 and 17 (along with all their respective subsequent calls) complete execution.

Recursion may seem overwhelming at first and it may take time for you to get used to it. But once you get the hang of it, there’s nothing more wonderfully magic in programming than recursive functions. Don’t give up on them just because they seem difficult at first sight.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s