What is Recursion ?

Table of contents

Recursion is basically a technique of problem-solving in which a function calls itself again and again till a particular base case.

The function calls itself with the help of parameters and at each call, the value of the parameter decreases or increases based on the type of recursive call. Recursive calls take place based on a recursive function which may be derived based on some logic. Recursion also sounds similar to Mathematical Induction ( No worries if you do not know Mathematical Induction )

Recursion forms an important base for other data structures and algorithms like Binary Trees, Graphs, Dynamic Programming, Segment Trees, etc. Generally while solving a problem via recursion, '' solve the problem at your level, pass the decreased form of the problem to your children for getting results from them, and then finally merge your and your children's solution and return it. " The problem-solving skill resides in the way of calling the children and the way of merging all the solutions.

The central idea of Recursion is forming a recursive function and visualizing the way in which recursive calls take place.

Recursive function

Assume a function 'f', which takes a parameter n where n is a positive integer. Now the main function 'f' will break itself into smaller sub functions and will call them for respective solutions. After getting the solutions from the sub-problems, the main function which is called the sub-problems will combine the respective solutions. The same logic is again applied to each of the sub-problems.

example, f(n) = max( f(n-1) , f(n-2) , f(n-3) ) , n > 0

0, n <= 0

Points to be noted in the above recursive function.

1) The sub problems of the main problem f(n) are f(n-1) , f(n-2) and f(n-3) . Similarly, for f(n-1) ( one of its children), the recursive call will be of the form

f(n-1) = max( f(n-2) , f(n-3) , f(n-4) )

2) The combining logic here is taking the max of its sub-problems' results. It can even be some other logic that may be based on combinations or which may take more time than a constant time. It requires good problem-solving skills for understanding how to merge the solutions of the subproblems.

3) The base case. As n is a positive integer so if it takes a negative value then will return a value directly ( 0 value here ). Based on the demand of the required problem one has to think about the base case.

It is important to note the recursion here is in a top-down manner where from a big value we are going towards a small value.

Similarly, the recursive function can also be of a bottom-up manner where from a small value we are going towards a big value.

example f(n) = max( f(n+1) , f(n+2) , f(n+3)

Visualizing recursion

Inside the memory, the recursive calls take place with help of stack data structure. Every time a call to any subproblem is made a new node is pushed into the stack and when the subproblem completes its work it is popped off.

For example, consider the recursion function for the sum of first n natural numbers.

f(n) = n + f(n-1) , n > 1

1 , n = 1

Look at the below figure for visualizing a recursive call

In the example given above the main function f(n) is calling only one sub-function, f(n-1). It may happen that the main function may call more than one of its sub functions. Such recursive calls are better visualized if done in a form of a binary tree-like structure. It is important to note that the in the stack structure only one node can be pushed or popped at a time and the recursive call happens in a depth-first search-like manner.

When to use Recursion?

  1. The recursive technique generally helps in understanding other important data structures and algorithms like Binary Trees, Graph, Dynamic Programming, Segment Trees, etc. All such algorithms and data structures use recursion.

  2. Recursion can be used when the time constraint of a problem is small as recursion takes exponential time in many cases.

  3. It can also be used when we have to print or show all the required possible arrangements or combinations.

  4. Recursion uses stack data structure, so care also has to be given to memory constraints.