What is Recursion?

Introduction

In computer programming, recursion is a strong idea that includes solving a problem by splitting it up into smaller, simpler versions of itself. Many examples from everyday life can be used to illustrate the idea of recursion, like how a tree branch splits into smaller branches and how a maze can be cleared by continuously examining ever-tinier sections of it.

Recursion is a programming technique that enables a function to call itself to solve a problem. This can be a very effective strategy since it enables us to break down big problems into smaller, more manageable sub-problems, allowing us to find solutions to those difficulties.

We will delve deeper into the idea of recursion in this article, looking at its anatomy, some of its limitations, types, and applications. You ought to know more about Recursion by the time this article is over and how to apply it to address various programming issues.

Recursion is a programming technique in which a function calls itself during execution. The concept of recursion is based on solving a problem by breaking it down into smaller sub-problems that can be solved using the same method.

A recursive function consists of two components: a base case and a recursive case. The base case is the basic case that can be solved directly without the need for further recursion. The recursive case is the one in which the function calls itself, passing a smaller version of the problem as a parameter.

During the execution of a recursive function, each recursive call creates a new instance of the function on the program stack. This stack of function calls is called the call stack. The call stack is used to keep track of the state of the program as it moves through the recursion. The below image shows the working of recursion.

Recursion Example

Let’s understand the Fibonacci sequence, in which each number is the sum of the two previous numbers. For the n-1th and n-2th numbers in the sequence, the recursive function that calculates the nth number in the series would make two calls to itself. The function can simply return 1 in the base case of n=1 or n=2.

def fibonacciRecursiveFunction(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacciRecursiveFunction(n-1) + fibonacciRecursiveFunction(n-2)

Types of Recursion

Tail Recursion

The recursive function where the recursive call is at the end of the function is called tail recursion. After the recursive call, no other operation is performed. It is more efficient than regular recursion because it allows for tail call optimization. To use tail recursion, it is necessary to structure the recursive function so that the last operation is the recursive call. Let us see a code snippet for it

def fibonacci(n, a=0, b=1):
   if n == 0:
       return a
   elif n == 1:
       return b
   else:
       return fibonacci(n-1, b, a+b)

In the above code, no other operation is performed after the recursive call.

Not-tailed Recursion

In this type of recursion, the recursive call is not the last operation performed in a function. Which means that the recursive call is not in the tail position of the function call. Let us see a code snippet for it:

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

In the above code, after the recursive call, the multiplication operation takes place.

Need of Recursion

Recursion is needed to:

Solve complex problems: Recursion is mainly used to break down complex problems into smaller sub-problems and solve the. It generates a more accurate solution by breaking the problem.
Simplify the code: Recursion breaks down the problem into smaller sub-problems, generating a more precise and elegant solution. We don’t have to repeatedly call the function, resulting in a cleaner code.
Handle hierarchical structure: Hierarchical structures such as graphs and trees can be handled more efficiently with the help of recursion. The recursive function can be called at each node which simplifies the complexity of the looping mechanism.
Solve divide and conquer problems: The sorting algorithms solve problems by the divide and conquer approach. Recursion helps solve those problems by dividing the problem into smaller subproblems. Also, handle it more efficiently and with less complexity.

Applications of Recursion

Some applications of Recursion are:

Mathematical Operations: Mathematical operations such as factorial, Fibonacci, permutation, combination, and exponential numbers can be calculated with the help of recursion. Recursive algorithms are often concise and elegant for solving such mathematical problems.
Tree and Graph Traversal: Recursion is best to solve dynamic problems related to binary trees, pre-order, post-order, in-order, or graphs like depth-first search and breadth-first search. They are commonly used to traverse trees and graph data structures.
File and Directory Operations: In order to search, delete, copy, or move files, recursive functions are used. For example, searching for a specific file in a nested folder structure can be implemented using recursion to traverse the directories until the file is found.
Dynamic Programming: Recursion is used in dynamic programming. It can be used to efficiently solve these subproblems and store the results to avoid redundant computations.
Backtracking: Recursive algorithms are used in solving backtracking problems like the N-Queens problem, Sudoku, and maze solving. These problems involve making a series of choices at each step and exploring all possible options until a good solution is found or all choices are exhausted.

Advantages of Recursion

Some advantages of Recursion are

Simplified Code: Recursive algorithms are known to be more simplified than any other algorithm. It can often lead to more concise and accurate code compared to iterative solutions.
Code Reusability: When a recursive function is implemented, it can be easily reused to solve similar problems with different inputs. Recursive functions solve complex problems by breaking them down into smaller subproblems. It reduces code duplication and promotes code reusability.
Time and Space Efficiency: Recursive functions can optimize memory usage by removing the need for an explicit data structure, such as a stack or a loop counter. Therefore, in some cases, recursion leads to more efficient solutions than iterative approaches.
Readability and Maintainability: Recursive code are known to be readable and easier to understand than iterative code. It can express the underlying problem-solving approach more intuitively, which makes the code easier to understand and maintain over time.

Disadvantages of Recursion

Although there are many advantages of recursion, there are some disadvantages as well:

Stack Overflow: The most common disadvantage of recursion is it can cause stack overflow if the function calls itself too many times or the depth of recursion is too high.
Performance Issues: The maintenance of stacks for each recursive call can slow down the program. Recursive function calls more memory than iterative functions.
Debugging Can be Challenging: The debugging of recursive functions can be difficult because of the complex stack. It is difficult to track the values at each level of recursion.
Limited Scalability: The number of recursive calls required to solve the problem increases exponentially. Therefore, it is not practical for some applications. It is not scalable for large input sizes.
Code Readability: Recursive code can be hard to follow the control flow of the program and understand how the recursion is working. It is difficult to read and understand.

Properties of Recursion

The key properties of recursion are:

Base case

A base case is a condition where the function returns a value instead of recursive calling itself. We can’t write a recursive function without a base case. Otherwise, it will create an infinite loop and result in a stack overflow error.

Divide and conquer

Recursion involves dividing a problem into smaller sub-problems similar to the original problem. Each sub-problem is solved using the same algorithm as the original problem, and the results are combined to form the final solution.

Function calls itself

Recursion involves calling the same function from within the function itself. This allows for a problem to be broken down into smaller sub-problems that can be solved using the same algorithm.

Stack overflow

One important thing to remember when using recursion is the risk of stack overflow errors. Each recursive call to the function adds a new frame to the stack, and if too many frames are added, the stack will overflow, causing the program to crash.

Memory usage

Recursion can be memory-intensive, as each recursive call creates a new stack frame, which uses memory. If the recursive function is called too many times, it can lead to high memory usage.

Tail recursion

Tail recursion is a special type of recursion where the recursive call is the last statement in the function. This allows some compilers to optimize the code by eliminating the need for new stack frames, reducing memory usage, and improving performance.

Anatomy of Recursive Function

The components of a Recursive function:

Base Condition

A base case, also known as a stopping case, is a condition in a recursive function that stops the recursion from continuing. It is an essential component of any recursive algorithm, as, without it, the function will keep calling itself indefinitely and may lead to a stack overflow error. The base case represents the simplest version of the problem that the recursive function aims to solve. Let us see the code for factorial to understand it better:

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

In the above code, the base case is when n reaches the value 0 it will return 1
We need to ensure that the base case is specified and that it will eventually be reached. If the base case is not specified, the function could run indefinitely and consume all available resources, causing the program to crash.

Recursive Call

A recursive case is a condition in a recursive function that calls itself with a modified version of the input. It is the other part of a recursive function, along with the base case, and it allows the function to break down a complex problem into smaller and more manageable sub-problems. Let us see if we don’t add the base case in the above factorial code,

def factorial(n):
   return n * factorial(n-1)

In this case, the function will enter an infinite loop when n is equal to 0 or less, which will eventually lead to a "stack overflow" error.

Working of a Recursive Function

When a recursive function is called, it executes its code until it reaches a point where it needs to solve a smaller version of the same problem. At this point, it calls itself with the smaller problem as input, which starts a new instance of the function on the call stack. Let us see the working of factorial code:

Let us assume we run the above function to find a factorial of 5. The function will execute as:

Step 1. factorial(5) calls factorial(4) with n-1, which is 4.

Step 2. factorial(4) calls factorial(3) with n-1, which is 3.

Step 3. factorial(3) calls factorial(2) with n-1, which is 2.

Step 4. factorial(2) calls factorial(1) with n-1, which is 1.

Step 5. factorial(1) calls factorial(0) with n-1, which is 0.

Step 6. factorial(0) returns 1 to factorial(1).

Step 7. factorial(1) returns 1 * 1 to factorial(2).

Step 8. factorial(2) returns 2 * 1 to factorial(3).

Step 9. factorial(3) returns 3 * 2 to factorial(4).

Step 10. factorial(4) returns 4 * 6 to factorial(5).

Step 11. factorial(5) returns 5 * 24, which is 120.

Hence the output will be 120.

Memory Representation of Recursion

When a recursive function is called, a new instance of the function is pushed onto the call stack. Each instance of the function is associated with its own set of variables and parameters, which are stored in memory.

As the recursive function executes, additional instances of the function are pushed onto the call stack, with each instance holding its own set of variables and parameters. Once the base case is reached, the function begins to return its results, with each return value being used to calculate the final result of the original function call.

As the recursive function completes its execution and returns its results, the instances of the function are popped off the call stack, freeing up the associated memory. This continues until all instances of the function have been removed from the call stack, and the memory that was allocated to store their variables and parameters is released.

It's important to note that if the recursion depth becomes too large, the call stack may become full, and the program may crash due to a stack overflow error. This can occur when a recursive function calls itself too many times or when the base case is not properly specified, causing the recursion to continue indefinitely.

StackOverflow problem

The stack overflow error is the major problem faced in recursive programming. It occurs when the depth of a function is too large and exceeds the amount of memory allocated to it. Every recursive call puts a layer of a stack in the memory. When the stack size is exceeded, it leads to a stack overflow error.

The recursive call stores each local variable, global variable, and return address for every recursive call, when it reaches the base case, it returns the saved return address. Let us understand it with the help of an example:

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

In the above example, the depth of recursion is 70000. Here the recursive function is called 70000 times, the stack would run out of space and will result in a stack overflow error.

In order to avoid the error, it is advised to write your code efficiently and make sure the depth of the function is under reasonable limits.

Recursive vs Iterative Calls

Properties	Recursive	Iterative
Control flow	It uses stack	It uses loops
Memory usage	It consumes more memory	It consumes less memory than a recursive call
Readability	They are easier to read	They are complex to read
Stack Overflow	It can cause a stack overflow	It cannot cause a stack overflow

Difference between direct and indirect recursion

The difference between direct and indirect recursion is:

Direct Recursion	Indirect Recursion
A function directly calls itself during its execution.	A group of functions or methods call each other in a circular manner, eventually leading to a recursive call to the initial function.
A function explicitly invokes itself within its own code.	Functions call one another in a chain or loop, and this chain ultimately leads to a call back to the original function or a cyclic calling pattern among multiple functions.
A classic example of direct recursion is the calculation of the factorial of a number	Indirect recursion might occur in a group of functions that collaborate to perform a task, such as functions A, B, and C, where A calls B, B calls C, and C calls A again.
It often involves a straightforward recursive logic within a single function.	It can be more complex to analyze and implement, as it requires understanding the flow of control between multiple functions.

Must Read Recursion in Data Structure

Frequently Asked Questions

What is recursion with example?

Recursion is a method where a function calls itself and breaks down a problem into sub-problems. For example, quick, merge, and heap sorting algorithms uses recursive functions and also dynamic problems like graphs and trees.

What is recursion in programming?

Recursion is when a function calls itself until it reaches a stopping point. It's used to solve problems by breaking them down into smaller subproblems. It has a base case that stops the recursion and a recursive case that calls itself with modified arguments. Recursion can be useful, but it may also have limitations like stack overflow errors and inefficiency.

What is the recursion in C?

Recursion in C is a programming technique where a function calls itself until a specific condition is met. By using recursion to traverse data structures such as trees and graphs, we can write elegant and concise code that is easy to understand and maintain. In order to write a recursive function, you must make sure that it has a base case. Also, the function must change its return values towards the base case.

Conclusion

In this article, we learned deeply about recursion. We studied about its anatomy, working, and memory representations. Recursion is a method in which we can solve problems by breaking them down into smaller subproblems. However, it is essential to remember the potential drawbacks of recursion, such as the risk of stack overflow and its inefficiency compared to iterative solutions.