Recursion

Recursion is the process of solving a computational problem by repeatedly calling a function from within the function until the desired output is achieved. Recursive programming is mostly used to apply the same type of logic multiple times to find a solution.

Recursion is the process that we need to learn to better understand Data Structures and Algorithms. Many of the data structure operations like search, traversal, etc uses the repetitive process to navigate through the nodes and find the solutions and this can be achieved using Recursion.

Stack overflow error for recursion in some programming languages

Multiple Recursion (Refer Recursion Types) may not be widely used in some of the most popular programming languages. While doing the actual code implementation for many of the well-known algorithms also, multiple recursive function calls are avoided and replaced with loops for such languages.

This is because of the way these languages are implemented. Here, till a function is completed all the variables used are stored in the stack space. This means that when a function calls itself, each call is considered as a separate function and variables gets stored in memory. Since all the functions are still in the execution mode till the final output is reached, the stack space is not cleared and keeps on increasing. And this results in stack overflow exception, if the number of iterations required are too high.

To handle this scenario, many such languages sets a default limit for recursive calls. For example, in Python the default recursion limit is 1000. Although we can increase it, it is not recommended.

Now, you may be wondering why learn recursion then. Because, recursion is the most elegant way to represent a repetitive task that forms the basis of most of the Data Structure Algorithms. It is easier to understand for beginners and code is usually shorter. Even if you are not going to use recursion in your code, a basic idea about recursion helps to better understand the DSA.

And some functional programming languages like Clojure does not even have loops. These languages use recursion to achieve the looping functionality and is as efficient as the languages that use the control structures like while or for. Such languages are designed to manage memory efficiently for recursive calls.
Base case in Recursion

For every recursive function there should be at-least one base case. Base case can be simply explained as a condition that stops the recursion and produces an output. A recursive function without a base case or if the code has some flows that prevents hitting of the base case, execution keeps on running till stack overflow error is thrown or the execution limit set by the programming language compiler is reached.

For the below code sample in Python that displays a Fibonacci series, if n <= 1: is the base case to exit the recursion.
Copied

def fib(n): if n <= 1: return n else: return fib(n - 1) + fib(n - 2) limit = 10 for i in range(1, limit): print(fib(i))
Types of recursion

Single Recursion : Only one self reference. Examples include, linear search, factorial computation, etc.

Multiple Recursion : Has more than one self reference. Can result in stack overflow exception in some programming languages for larger set of iterations. Example usages can be found in tree traversals, bubble sorts, etc.

Indirect Recursion : Indirect recursion happens when a function calls another function and from within the second function, first one gets called.

Tail Recursion : Such functions make the recursive calls only as the last statement of the function. Such type of recursions are useful in some programming languages that treats such calls as iterative jumps rather than a new function call, thereby using the same memory space for better memory utilization.

Alternatives to recursion

We can use Iterators such as for and while to eliminate recursive functions. Iterators provide better memory usage in case of some programming languages. For some others, recursive function calls are as optimized as that of loops and recursion can be used without any concerns.

See below a sample code to find the factorial using recursion and without recursion.

Using recursion

def factorial(n):
    if n == 1:
        return n
    else:
        return n * factorial(n - 1)

f = 5
print("Factorial of {0} is {1} ".format(f, factorial(f)))

public class Factorial
{
    public static void main(String[] args) {
        int f = 5;
    System.out.println("Factorial of " + f + " = " + factorial(f));
    }
    
    public static long factorial(int n)
    {
        if (n == 1)
            return n;
        else
            return n * factorial(n - 1);
    }
}

using System;

namespace Factorial
{
    class Program
    {
        static void Main(string[] args)
        {
            int f = 5
            Console.WriteLine("{Factorial of {0} is {1}", f, factorial(f));
        } 

        private static long factorial(int n)
        {
            if (n == 1)
                return n;
            return number * factorial(n-1);

        }
    }
}

function factorial(n) {
    if (n == 1)
        return n;
    else
        return n * factorial(n - 1);
}

f = 5;
alert(factorial(f));

Without recursion

f = n = 5
fact = 1
while (f > 0):
    fact = fact * f
    f -= 1

print("Factorial of {0} is {1} ".format(n, fact))

public class Factorial
{
    public static void main(String[] args) {
        int f = 5;
        int n = f;
        int fact = 1;
        while (f > 0) {
            fact = fact * f;
            f -= 1;
        }
        System.out.println("Factorial of " + n + " = " + fact);
    }
}

using System;

namespace Factorial
{
    class Program
    {
        static void Main(string[] args)
        {
            int f = 5;
            int n = f;
            int fact = 1;
            while (f > 0) {
                fact = fact * f;
                f -= 1;
            }

            Console.WriteLine("{Factorial of {0} is {1}", n, fact);
        }
    }
}

f = 5;
fact = 1;
while (f > 0) {
    fact = fact * f;
    f -= 1;
}

alert(fact);

Recursion

Stack overflow error for recursion in some programming languages

Base case in Recursion

Types of recursion

Alternatives to recursion

Using recursion

Without recursion