Recursion | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

What is Recursion?

The process where a function calls itself, either directly or indirectly, is known as recursion, and the corresponding function is called a recursive function.

• Through a recursive algorithm, certain problems can be solved easily. Examples include 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, thereby tackling smaller subproblems of the original problem.
• Additional recursive calls are generated as needed.
• It's crucial to provide a base case to terminate the recursion process.
• So, each time the function calls itself, it deals with a simpler version of the original problem.

Need of Recursion 

• Recursion is a remarkable technique that helps reduce code length and enhances readability and writing simplicity.
• It offers distinct advantages compared to iteration, which will be explored later.
• When dealing with a task and its similar subtasks, recursion proves to be one of the most effective solutions.
• For instance, consider the example of calculating 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 infinite loop will occur.

Algorithm Steps

The algorithmic steps for implementing recursion in a function are as follows: 
Step1 - 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. 
Step2 - 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. 
Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. 
step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.

A Mathematical Interpretation 

To add the numbers starting from 1 to n. So the function simply looks like this, 

There is a simple difference between the approach (1) and approach(2) and that is in approach(2) the function “ f( ) ” itself is being called inside the function, so this phenomenon is named recursion

How are recursive functions stored in memory? 

• Recursion tends to consume more memory as the recursive function contributes to the stack with each call, retaining values until the call concludes.
• The recursive function follows a Last In, First Out (LIFO) structure, similar to the stack data structure.

What is the base condition in recursion?  

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

How a particular problem is 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 Stack Overflow error occurs in recursion?  
If the base case is not reached or not defined, then the stack overflow problem may arise.  

What is the difference between direct and indirect recursion?  

How memory is allocated to different function calls in recursion?  

• When a function is invoked from the main(), memory is assigned to it on the stack.
• In the case of a recursive function, each self-invocation results in memory allocation atop the calling function's memory, creating distinct copies of local variables for each call.
• Upon reaching the base case, the function returns its value to the calling function, leading to memory deallocation. This process continues accordingly.
• Many programming languages utilize stacks to implement recursion.
• When a function (caller) invokes another function (callee), or itself as the callee, the execution control is transferred from the caller to the callee.
• This transfer may involve passing data from the caller to the callee.
• As a result, the caller function temporarily suspends its execution and resumes later when control returns from the callee function.
• To ensure the caller function resumes from the exact point where it paused, and with the same data values, an activation record (or stack frame) is created for the caller function.

Recursion VS Iteration 

Mathematical Equation:  

n if n == 0, n == 1;      fib(n) = fib(n-1) + fib(n-2) otherwise;

Recurrence Relation: 

T(n) = T(n-1) + T(n-2) + O(1)

Recursive program: 

Input: n = 5 Output:
Fibonacci series of 5 numbers is : 0 1 1 2 3

Implementation: