Recursion | Programming and Data Structures - GATE CSE Notes

The function which calls itself is called recursive function. Recursion is used to solve different problems in mathematics by dividing them into smaller problems, this is called Divide and Conquer method.

What You Learn about Recursion :

- What is Recursion? - Simple Explanation
- TYPES OF RECURSION 
- C Program example of Recursion
- Practice Questions for Recursion - MCQ

What is Recursion?

- Function calls itself is called recursion.
- The function which calls itself is called recursive function.
- Recursion is used to solve different problems in mathematics by dividing them into smaller problems, this is called Divide and Conquer method.
- Recursion is used in programming to divide complicated problems into simpler ones and solve them individually.
- In order to prevent an infinite recursive call, we need to define the correct exit condition (Base condition) in the recursive function. We can use if…else or other conditional statements to create exit condition.
- Infinite recursive calls may lead to system crash. Infinite iteration may not lead to system crash but stop the execution of program when memory is exhausted.
- Stack overflow problem may arise, if base case/exit condition is not defined or poorly defined.
- Time complexity of the Recursion can be determined by finding the value of the nth recursive call in terms of the previous call. Calculating the Time complexity of Recursion is more complicated than iteration.
- Recursion is desirable for smaller code size, but has more time complexity.
- Using recursive algorithm, problems like DFS of Graph, Towers of Hanoi,  Inorder/ Preorder /Postorder Tree Traversals can be solved.
In general, in a recursive and non-recursive implementation of a problem (program), Both time and space complexities are better in non-recursive than in recursive program.

Memory allocation in Recursive function calls:

- Whenever any function is called, memory is allocated to it on the stack. 
- The memory for a called function is allocated on top of memory allocated to calling function. 
- At last when exit condition is reached, the function returns its final value to the calling function and memory is de-allocated.

Syntax of Recursion function:

Recursion | Programming and Data Structures

TYPES OF RECURSION

  • Direct Recursion
  • Indirect Recursion
Recursion, Types of recursion, data structure


Direct recursion: 
A function is said to be direct recursive if it calls itself directly.

Indirect Recursion: 
A function is said to be indirect recursive if it calls another function and this new function calls the first calling function again.

C Program example of Recursion to find factorial of given number with explanation:

#include<stdio.h>
#include <conio.h>
int factorial(int p)
{
if(p==0)
return 1;
else
return (factorial(p - 1)*p);
}

int main()
{
int number,fact;
printf("Enter a number: ");
scanf("%d",& number);
fact = factorial(number);
printf("Factorial of an entered Number %d = %d", number, fact);
getch();
}

Output:
Enter a number: 8
Factorial of an entered Number 8 = 40320

Explanation of above c recursion program:

In this C recursion program, the factorial is calculated using recursion.
- The formula for calculating factorial of a given n number is,
- n! = 1*2*...(n-1)*n
- Again, we can see
- (n-1)! = 1*2*...(n-1)
- Hence, we can write,
- n! = (n-1)! * n
- We have implemented this recursive relation in our program.
Here,
- Number is stored in variable p to find its factorial.
- A recursive function factorial(number) calculates the factorial of the entered number.
- As factorial is (n-1)! * n, factorial function calculates the factorial by recursively multiplying n with factorial of (n-1).
- Finally, when n = 0, it returns 1 because 0! = 1.
- Here, base condition or exit condition is if(p==) to make sure that, recursive function not entered in infinite state.

Practice Questions for Recursion:

Multiple Choice Questions (MCQ) On Recursion:

Q1 on Recursion:  
Consider the following recursive C function that takes two arguments
unsigned int foo(unsigned int n, unsigned int r)
{
if (n > 0) return (n%r + foo (n/r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo( 345, 10) ?
GATE CS 2011

A. 345
B. 12
C. 5
D. 3

ANS: B. 12 

Solution: 












- In above question, Function foo(n, 10) returns sum of digit of number n.

Q2 on Recursion:
Consider the recursive C function that takes two arguments
unsigned int foo(unsigned int n, unsigned int r) {
if (n > 0) return (n%r + foo (n/r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo(513, 2)? - GATE CS 2011
A. 9 
B. 8
C. 5
D. 2

ANS: D. 2 

Solution: 

Data Structure Questions and Answers – Recursion, Recursion Gate topic, GATE DATA STRUCTURE Recursion notes

 - Function foo(n, 2) returns sum of bits in the number n.

Q3 on Recursion:

#include<stdio.h>
int f(int *a, int n)
{
if(n <= 0) return 0;
else if(*a % 2 == 0) return *a + f(a+1, n-1);
else return *a - f(a+1, n-1);
}

int main()
{
int a[] = {12, 7, 13, 4, 11, 6};
printf("%d", f(a, 6));
getchar();
return 0;
}

- GATE CS 2010

A. -9
B. 15
C. 5
D. 19


ANS: B. 15

Solution: 
- f(int *a, int n) is a recursive function. if(*a % 2 == 0) is true, means *a is even. Then *a + f(a+1, n-1) will executed. if(*a % 2 == 0) is false, means *a is odd. Then if(*a % 2 == 0) *a - f(a+1, n-1) will be executed.
Here, given in main function
     int a[] = {12, 7, 13, 4, 11, 6};
     printf("%d", f(a, 6));
- a contains address of 12 in a[] array, a+1 contains address of 7
- let's see recursive tree of this function:

Practice Questions for Recursion

Return value : is 12 + (7 – (13 – (4 + (11 – (6 + 0))))) = 15

Hope You find this article very helpful to prepare Recursion concept of Data structure. Keep Learning, Keep Sharing, keep Visiting this blog 😍.

Post a Comment

0 Comments