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 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:

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.