Introduction to Recursion

What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion, and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A recursive function solves a particular problem by calling a copy of itself and solving smaller subproblems of the original problems. Many more recursive calls can be generated as and when required. It is essential to know that we should provide a certain case in order to terminate this recursion process. So we can say that every time the function calls itself with a simpler version of the original problem.

Need of Recursion

Recursion is an amazing technique with the help of which we can reduce the length of our code and make it easier to read and write. It has certain advantages over the iteration technique which will be discussed later. A task that can be defined with its similar subtask, recursion is one of the best solutions for it. For example; The Factorial of a number.

Properties of Recursion:

Performing the same operations multiple times with different inputs.
In every step, we try smaller inputs to make the problem smaller.
Base condition is needed to stop the recursion, otherwise an infinite loop will occur.

Algorithm: Steps

Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself.
Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem.
Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop.
Combine the solutions: Combine the solutions of the subproblems to solve the original problem.

A Mathematical Interpretation

Let us consider a problem that a programmer has to determine the sum of the first n natural numbers. There are several ways of doing that, but the simplest approach is simply to add the numbers starting from 1 to n. So the function simply looks like this:

f(n) = 1 + 2 + 3 + … n

But there is another mathematical approach of representing this:

f(n) = 1                  n=1

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

There is a simple difference between the two approaches, and that is in the second approach, the function "f()" itself is being called inside the function, so this phenomenon is named recursion, and the function containing recursion is called a recursive function. At the end, this is a great tool in the hands of programmers to code some problems in a lot easier and efficient way.

How are recursive functions stored in memory?

Recursion uses more memory because the recursive function adds to the stack with each recursive call and keeps the values there until the call is finished. The recursive function uses the Last In First Out (LIFO) structure just like the stack data structure.

For more information, see: Stack Data Structure

What is the base condition in recursion?

In the recursive program, the solution to the base case is provided, and the solution to the bigger problem is expressed in terms of smaller problems.

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

In the above example, the base case for n <= 1 is defined, and the larger value of a number can be solved by converting it to a smaller one until the base case is reached.

How is a particular problem solved using recursion?

The idea is to represent a problem in terms of one or more smaller problems and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know the factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Why does a Stack Overflow error occur in recursion?

If the base case is not reached or not defined, then the stack overflow problem may arise. Let us take an example to understand this:

        int fact(int n)
        {
            // wrong base case (it may cause
            // stack overflow).
            if (n == 100) 
                return 1;
            else
                return n * fact(n-1);
        }

If fact(10) is called, it will call fact(9), fact(8), fact(7), and so on, but the number will never reach 100. So, the base case is not reached. If the memory is exhausted by these functions on the stack, it will cause a stack overflow error.

What is the difference between direct and indirect recursion?

A function is called direct recursive if it calls the same function. A function is called indirect recursive if it calls another function, say fun_new, and fun_new calls the original function directly or indirectly.

        // An example of direct recursion
        void directRecFun()
        {
            // Some code....

            directRecFun();

            // Some code...
        }

        // An example of indirect recursion
        void indirectRecFun1()
        {
            // Some code....

            indirectRecFun2();

            // Some code...
        }
        void indirectRecFun2()
        {
            // Some code....

            indirectRecFun1();

            // Some code...
        }

What is the difference between tailed and non-tailed recursion?

A recursive function is tail recursive when a recursive call is the last thing executed by the function. Please refer to the tail recursion article for details.

How is memory allocated to different function calls in recursion?

When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, and the memory for a called function is allocated on top of the memory allocated to the calling function, creating a different copy of local variables for each function call.

For more information, see: Stack Data Structure

Recursion vs. Iteration

SR No.	Recursion	Iteration
1)	Terminates when the base case becomes true.	Terminates when the condition becomes false.
2)	Used with functions.	Used with loops.
3)	Every recursive call needs extra space in the stack memory.	Every iteration does not require any extra space.
4)	Smaller code size.	Larger code size.

Advantages and Disadvantages of Recursive Programming

Disadvantages of Recursive Programming

Note that both recursive and iterative programs have the same problem-solving powers, i.e., every recursive program can be written iteratively and vice versa is also true. The recursive program has greater space requirements than the iterative program as all functions will remain in the stack until the base case is reached. It also has greater time requirements because of function calls and returns overhead. Moreover, due to the smaller length of code, the codes are difficult to understand, and extra care has to be practiced while writing the code. The computer may run out of memory if the recursive calls are not properly checked.

Advantages of Recursive Programming

Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. For such problems, it is preferred to write recursive code. We can write such codes also iteratively with the help of a stack data structure. For example, refer to Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

Summary of Recursion