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.Recursion | Programming and Data Structures - Computer Science Engineering (CSE)

  • 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, 

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

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?  

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

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.  
Recursion | Programming and Data Structures - Computer Science Engineering (CSE)

What is the difference between direct and indirect recursion?  

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


Recursion | Programming and Data Structures - Computer Science Engineering (CSE)Recursion | Programming and Data Structures - Computer Science Engineering (CSE)
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 | Programming and Data Structures - Computer Science Engineering (CSE)Recursion VS Iteration 
Recursion | Programming and Data Structures - Computer Science Engineering (CSE)

Problem 1: Write a program and recurrence relation to find the Fibonacci series of n where n>2 .

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: 

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

The document Recursion | Programming and Data Structures - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Programming and Data Structures.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
91 docs|30 tests

Up next

Arrays
Doc | 6 pages
Stacks
Doc | 5 pages
Queues
Doc | 5 pages

FAQs on Recursion - Programming and Data Structures - Computer Science Engineering (CSE)

1. What is recursion in computer science?
Ans. Recursion is a programming technique where a function calls itself in order to solve a problem. It involves breaking down a problem into smaller subproblems and solving them recursively.
2. What are the properties of recursion?
Ans. The properties of recursion include base case (stopping condition), recursive case (function calling itself), and progress towards the base case (reducing problem size with each recursive call).
3. How is recursion implemented in programming languages?
Ans. Recursion is implemented in programming languages by defining a function that calls itself within its body. This allows the function to repeatedly execute until a base case is reached.
4. What is the time complexity of recursive algorithms?
Ans. The time complexity of recursive algorithms depends on the number of recursive calls made and the work done within each call. It can be analyzed using techniques like recurrence relations or master theorem.
5. What is the space complexity of recursive algorithms?
Ans. The space complexity of recursive algorithms depends on the maximum depth of the recursion tree and the space required for each recursive call. It is important to consider memory usage when working with recursive functions.
91 docs|30 tests
Download as PDF

Up next

Arrays
Doc | 6 pages
Stacks
Doc | 5 pages
Queues
Doc | 5 pages
Explore Courses for Computer Science Engineering (CSE) exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Previous Year Questions with Solutions

,

pdf

,

shortcuts and tricks

,

practice quizzes

,

Viva Questions

,

past year papers

,

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

,

video lectures

,

Exam

,

Summary

,

Sample Paper

,

Extra Questions

,

ppt

,

mock tests for examination

,

Important questions

,

MCQs

,

Semester Notes

,

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

,

Free

,

Objective type Questions

,

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

,

study material

;