Loop Control Statements in C
Introduction to HTML
How to use the Github API
The image tag, anchor tag and the button tag
Ordered and Unordered Lists in HTML
The division tag
HTML Forms
Tables in HTML
Introduction to C Programming
Introduction to Python
Varibles and Datatypes in Python
Operators in Python
Typecasting in Python
Input and Output in Python
If Else in Python
Loops in Python
Break, Continue and Pass in Python
Python practice section 1
Lists in Python
Tuple in Python
Recursion
Suppose you are standing in a queue and you want to know the number of
people standing in the queue. You cannot directly count the number of
persons but if you the number of people standing in front of you then
you know that The total number of people in the queue = The number of
people ahead you + 1 (including you). But how will you know the number
of people ahead you ? You can ask the person standing ahead you. That
person also doesn't know the number of person ahead him so he asks the
person in front of him and so on. The queue has limited persons so
when the second person asks the first person that how many people are
ahead you, then the first person says 0. Now, the first person has
given his answer to the second person. So, the second person replies
to the third person by saying that there are (0+1) persons standing in
front of him (by including the first person). The third person replies
to the fourth person by saying there are (1+1) two persons in front of
him (ny including the second person) and so on till the last person.
The process happening above is known as recursion. No person standing
in the queue knows the answer expect the first one. So,they ask the
person in front of them add 1 to it and get their own answer. Here,
the answer of one of them is dependent on the other. When one person
does not know the answer, he asks the person on his front and so on.
When one person knows the answer, he gives it to the person behind him
and so on until the final answer is obtained. The thing to remember
here is that there is atleast one person who knows the answer. If
nobody knows the answer, then the problem cannot be solved.
- What is recursion ?
- Example #1
- Example #2
- Advantages and Disadvantages
Jump to specific sections
What is recursion ?
In programming terms, the process in which a function which calls
itself again and again is called as recursion. The problem is divided into subproblems
until the answer to the subproblem is known. After that, we keep merging the solution of the
subproblems to get the final answer.
For example -
#include<stdio.h>
void count_persons(person p)
{
if(there is no one standing in front of p) // Base condition
return 0 ;
else
{
return 1 + count_persons(the person standing in front of p) ; // Recursive call
}
}
void main() {
cout<<count_persons(the last person standing in the queue) ;
}
A recursive function must have a base condition i.e a subproblem whose solution is
already known. Without a base condition, the problem will keep on dividing and dividing
but no solution could be found. The program would be struck in an infinite loop. Hence,
the base condition must be defined clearly.
Example #1
Suppose you want to calculate the factorial of a number. We all know that :
n ! = n x (n-1) ! i.e if we know the value of (n-1) ! , we can compute n !
by multiplying n to it.
Lets see how we can do it in the recursive way -
#include <iostream.h>
int fact(int n)
{
if(n <= 1) // Base Condition
return 1 ;
else
return n * fact(n-1) ; // Recursive Call
}
void main()
{
int n;
cout<<"Enter a number : ";
cin>>n;
cout<<"Factorial of "<<n<<" = "<<fact(n);
}
Output
Enter a number : 10
Factorial of 6 = 720
The whole code can be understood by seeing this -
6 ! = 6 x fact(5)
6 ! = 6 x 5 x fact(4)
6 ! = 6 x 5 x 4 x fact(3)
6 ! = 6 x 5 x 4 x 3 x fact(2)
6 ! = 6 x 5 x 4 x 3 x 2 x fact(1)
6 ! = 6 x 5 x 4 x 3 x 2 x 1
6 ! = 6 x 5 x 4 x 3 x 2
6 ! = 6 x 5 x 4 x 6
6 ! = 6 x 5 x 24
6 ! = 6 x 120
6 ! = 720
6 ! = 6 x fact(5)
6 ! = 6 x 5 x fact(4)
6 ! = 6 x 5 x 4 x fact(3)
6 ! = 6 x 5 x 4 x 3 x fact(2)
6 ! = 6 x 5 x 4 x 3 x 2 x fact(1)
6 ! = 6 x 5 x 4 x 3 x 2 x 1
6 ! = 6 x 5 x 4 x 3 x 2
6 ! = 6 x 5 x 4 x 6
6 ! = 6 x 5 x 24
6 ! = 6 x 120
6 ! = 720
Example #2
Suppose you want to calculate the sum of numbers from 1 to n. We know that the
Sum of numbers from 1 to n = Sum of numbers from 1 to (n-1) + n.
Let's see how we can do it the recursive way.
#include <iostream.h>
int sum(int n)
{
if(n == 1) // Base condition
return 1;
else
return sum(n-1)+ n ; // Recursive call
}
void main()
{
int n ;
cout<<"Enter the value of n" ;
cin>>n ;
cout<<"Sum of numbers from 1 to n = "<<sum(n) ;
}
Output
Enter the value of n : 5
Sum of numbers from 1 to n = 15
The whole code can be understood by seeing this -
Sum(5)=Sum(4)+5
Sum(5)=Sum(3)+4+5
Sum(5)=Sum(2)+3+4+5
Sum(5)=Sum(1)+2+3+4+5
Sum(5)=1+2+3+4+5
Sum(5)=3+3+4+5
Sum(5)=6+4+5
Sum(5)=10+5
Sum(5)=15
Sum(5)=Sum(4)+5
Sum(5)=Sum(3)+4+5
Sum(5)=Sum(2)+3+4+5
Sum(5)=Sum(1)+2+3+4+5
Sum(5)=1+2+3+4+5
Sum(5)=3+3+4+5
Sum(5)=6+4+5
Sum(5)=10+5
Sum(5)=15
Advantages and Disadvantages
Advantages of recursion are -
Disadvantages of recursion are -
- It is easy to write and understand.
- Makes code shorter.
Disadvantages of recursion are -
- Takes additional stack space.
- Makes code difficult to debug.