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:
TYPES OF RECURSION
- Direct Recursion
- Indirect Recursion
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.
Direct recursion:
Indirect Recursion:
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 argumentsunsigned 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 argumentsunsigned 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:
- 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:
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:
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 😍.
0 Comments