Recursion Explained

Recursion….Recursion….Recursion

It is the most commonly heard term. How hard or how easy is recursion?!

Let’s take a look!!!

Recursion is the most important concept in the programming arena. It is made to solve problems that can be broken down into smaller, repetitive problems. It is used when anything has many branches, and the iterative approach becomes too complex.

Let's walk through a basic example for a better understanding of the recursion concept .

Consider we have a box that contains a box inside which in turn contains another box and so on. Imagine we have a key in any one of the boxes and the task is to find the key.

The recursive approach we follow for the above problem statement will go this way, we open a box and see for the key, if we find it then end the search, else we go to the next box(repeating the process). The function is to open the box and find the key, it has to be done repeatedly or it should be called continuously until we find the key. The pseudocode for the above can be written as

function open_box_and_see_for_key:
    if found:
        exit
    else:
        open_box_and_see_for_key()

Some common problems that use recursion are tree traversals like Inorder, preorder and postorder, Towers of Hanoi, Factorial, Depth first search, etc...

Base Case:

The base case is the situation where we return value and does not make any further calls to the function. It is a place where the process of recursion ends. Identifying a proper base case is very important as not doing so leads to memory overflow.

Whenever a function is called, it is stored in the stack. As the recursion makes repetitive calls to the function, it stores all the function calls in the stack, if there is no base case, it keeps on pushing the function to the stack, and the memory overflows. In the above example “finding the key” is the base case. If we find the key the process stops.

Types of recursion:

There are two types of recursion, Direct recursion, and Indirect recursion.

Direct recursion is the procedure where we call the same function repeatedly.

Indirect recursion is the procedure where a function calls another function and the called function in turn calls the calling function in any way.

function direct_recursion():
 ……
 ……
 direct_recursion();
 ……
 ……
function indirect_recursion_1():
 ……
 ……
 indirect_recursion_2();
 ……
 ……
 
function indirect_recursion_2():
 ……
 ……
 indirect_recursion_1();
 ……
 ……

If the recursive call is the last thing executed by the function, then it is called a tail-recursive function.

Thinking Recursively:

Let’s take the most basic and common example of recursion, i.e, finding the factorial of a number.

We can have 2 approaches here, iterative and recursive.

In the iterative approach, we loop from 1 to the desired number by multiplying all the numbers.

Now let's think it in another way, consider we need to find the factorial of n(the product of a number, let's say n and all the numbers below n).

factorial of (n) = n * factorial of (n-1)
factorial of (n-1) = (n-1) * factorial of (n-2)

Here the factorial of a number is defined as that number multiplied by factorial that number minus one(n-1) which in turn is multiplied by the factorial of that number minus one ((n-1)-1) and so on until we reach zero. It is divided into more subproblems and the base case is “when it reaches 0”. The factorial function is called repeatedly until the base case occurs.

#Iterative Approach
function iterative_factorial(int n):
 fact = 1
 while n>0:
 fact = fact * n
 n = n — 1
#Recursive Approach
function recursive_factorial(int n):
 if n == 0:
 return
 return n*recursive_factorial(n-1)

Another basic example of recursion can be a problem to check if a string is a palindrome or not. In the efficient iterative approach, we use two pointers begin and end, if the character at the begin and end are the same then we increment the value of begin by one and decrement the value of end by one until the begin pointer crosses the end pointer.

Now think the same problem recursively, consider the string as “MADAM”

Step 1: Check if the first and last character is the same, if yes, check if the remaining string is a palindrome( send the remaining string as parameter and call the function again).

Step 2: The remaining string is a palindrome if the first and last character is the same in the remaining string and the rest of the string is a palindrome

The same steps go on until the base condition satisfies.

#Iterative approach
function iterative_palindrome(string):
 while(begin<end):
 if string[begin] != string[end]:
 return False
 else:
 begin = begin + 1
 end = end + 1
#Recursive Approach
function recursive_palindrome(string, start, end):
 if start > end:
 return True 
 if string[start] != string[end]:
 return False 
 return recursive_palindrome(string, start+1, end-1)

Recursion is never a better way for a computer but it is always a better way for programmers. It takes greater space than iterative as all the function calls are stored in the stack until they are returned. If a problem takes 100 lines of code to solve in the iterative approach, it may take 3–4 lines in the recursive approach. Every recursive function can be written in iterative and vice versa.

HAPPY CODING!!!