Types Of Recursion:
- Direct Recursion
- Indirect recursion
- Tail Recursion
- Non-Tail Recursion
- Linear and Tree Recursion
1.Direct Recursion:
If a function calls the same function again is called as direct recursion .
int fun(){
//Statement
fun();
}
Code:
#include<stdio.h>
int fun(int n){
if(n==0)
{
return n;
}
printf(“%d\n”,n);
return fun(n-1);
}
int main()
{
fun(5);
return 0;
}
Output:
5
4
3
2
1
2.Indirect Recursion:
- If a function call to another function which ultimately calls to it .
- These two functions are indirectly recursive as they call each other .
Example:1
//INDIRECT RECURSION
#include<stdio.h>
int odd();
int even();
int n=1;
int main()
{
odd();
return 0;
}
int odd(){
if(n<=15){
printf(“%d\n”,n*2);
n++;
even();
}
return 0;
}
int even(){
if(n<=15){
printf(“%d\n”,n*5);
n++;
odd();
}
return 0;
}
Output:
2
10
6
20
10
30
14
40
18
50
22
60
26
70
30
3.Tail Recursion
- A function is said to be tails recursive if no operations are pending to performed when the recursive function return to its caller .
- A recursive function is called tail recursive is the last things done by the function .
if(n==0)
return;
else
print(“%d”,n);
return fun(n-1);
}
Note: There is no need to keep record of previous task .
Example:
//TAIL RECURSION
#include<stdio.h>
void fun(int n)
{
if(n==0)
{
return;
}
else
{
printf(“%d\n”,n);
}
return fun(n-1);
}
int main()
{
fun(5);
return 0;
}
Output:
5
4
3
2
1
4.Non-Tail Recursion
- A function is said to be non-tail recursive if some operation are pending to performed when the recursive function return to its caller .
- After returning back , there is something left to be evaluate .
Note: There is need to keep record previous task .
Example:
//NON-TAIL RECURSION
#include<stdio.h>
void fun(int n){
if(n==0)
{
return;
}
fun(n-1);
printf(“%d\n”,n);
}
int main()
{
fun(5);
return 0;
}
Output:
1
2
3
4
5