Recursion and Backtracking

Imagine yourself standing on a mountain cliff and calling your own name repeatedly. well, recursion is something similar.

Recursion occurs when a function calls itself in a repetitive fashion. A function is designed in such a way that it calls itself in its own body and such a function is called a Recursive function.

Well, one might imagine if a repetition occurs, there must be a terminating condition or else it might be infinite. This terminating condition is called the base case.

A base case is the case whose solution is pre-known and is used without computation. Without base case, infinite recursion occurs.

A recursive case is the case where the recursion occurs repeatedly calling the body of the function.

There are 2 main kinds of recursions - Direct recursion and Indirect recursion

Direct Recursion

When the function calls itself directly within its body , it is an example of direct recursion.

void recur()
{
	recur();
}

Indirect recursion

When a function calls another function , which calls its caller function is called Indirect Recursion.

void recur1()
{
	recur2();
}

void recur2()
{
	recur1();
}

Let's take an example of a recursive function to find factorial of a number :

we know, factorial of a number is a product of all numbers from 1 to n such that

n! = 1 * 2 * 3 * 4 * ................. * n

Hence we can conclude :  

n! = n * (n - 1)!

Hence it yields a recursive function having two main properties as follows :

1. if n = 0 then n! = 1
2. if n > 0 then n! = n * (n-1)!

Let's take an example of calculating the factorial of 3 given below :

Now, we have to understand the concept of backtracking to actually get the value of 3! which in explained below :

What is Backtracking in recursion ?

In some problems, while searching for a solution, we may reach a dead end and have to go back to a point where we can actually find the solution. Conceptually backtracking is easy but its tricky in programming . Recursive solutions are a natural fit in backtracking.

Example 1 : factorial of a number

Recursive function to find factorial of a number n

int fact(int n)
{
   if(n == 0)
   	return 1;  // base case
   else
   	return (n * fact(n - 1));  // recursive case
 }

Hence, the statement (n * fact(n - 1)) calls the function fact repeatedly in the same body using different arguments in order to have simultaneous product of the numbers which in turn returned to the caller as n reduces to 0.

Let's dry run to find the value of 5! as shown below using the concept of backtracking :

for n = 5 , the dry run is as follows :

Example 2 : Fibonacci series

Now let us take another example of a recursive function to generate elements of a Fibonacci  series up to a given limit :

int fib(int n)
{
   if(n == 1)
   	return 0;
   else if(n == 2)
   	return 1;
   else if(n > 2)
   	return (fib(n - 1) + fib(n - 2));
 }

Now , let us do dry run to find Fibonacci series up to limit n = 5

Now, we shall find the value to generate Fibonacci series till limit n = 5.

we shall use the concept of backtracking in recursion to do the dry run as given below in the diagram.

Hence we are able to generate the Fibonacci series up to 5th term.

Example 3 : power of a given number

Let us consider another example where we write a recursive function to find number raised to any power.

int power(int n, int p)
{
  if(p == 0)
  	return 1;
  else
  	return (n * power(n, p - 1));
}

Now let us do the dry run for n = 2 and p = 5 and let's see the output :

Hence, we are able to find the power using the concept of recursion and backtracking.

Example 4 : sum of first n natural numbers

Let us consider another example where we try to write a recursive function for sum of first n natural numbers :

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

Now let us dry run taking n = 5 and see :

Now let's see the backtracking to find the result :

How is recursion different from iteration ?

1. Recursion allows separate memory space allocation for each recursive call. While, iteration uses the same memory location for the variables.
2. Recursion takes more time as it is a slow process while iteration is time saving process as it is comparatively faster.
3. Recursion uses Stack for the concept of backtracking to represent all values, while iteration represents only the final value and all other previous values are wiped out.

Conclusion

We have come to the end of our discussion on recursion and backtracking. We have learnt how to dry run using backtracking to predict the output of a recursive function. Backtracking is not only limited to recursion but is also used in solving other maze programs which we shall later learn in data structures and algorithms.

If this blog was helpful to you, kindly subscribe and share with your friends.