Types of recursion
As we discoursed in the previous sessions, recursion is a process of executing a statement or multiple statements repeatedly by calling a function itself.
Recursion reduces the performance of program as it takes time to shift the control to a function and getting it back to the caller. It takes much space as recursion forward (winding). A termination statement is properly set to overcome from the problem of stack overflow.
In this session, we will discourse different ways of building recursion. Some of which are already discoursed in the previous sessions.
- Linear recursion
- Binary recursion
- Tail recursion
- Mutual recursion
- Nested recursion
Linear recursion
It is the most commonly used recursion, where a function calls itself in simple manner and a terminating condition is used to terminate the recursion. Forwarding recursion is called winding and getting the control back to the caller is called unwinding.
long factorial(int n)
{
int f;
if(n==1) /* terminating condition */
return 1;
f=n*factorial(n-1); /* calling function itself */
return f;
}
Binary recursion:
It is a type of recursion where function is called twice instead once in the recursive functions.
This type of recursive functions were used in implementing Towers of Hanoi, Binary search and Quick sort in the previous sessions.
/* Quick sort recursive function */
void qsort(int start,int end)
{
int s;
if(start>=end)
return;
s=split(start,end);
qsort(start,s-1); /* takes left sub array to split point */
qsort(s+1,end); /* takes right sub array to split point */
}
Tail recursion
It is the recursion where recursive function is called at the end of recursive function.
/* Recursive function for Fibonacci */
void fibonacci(int a,int b,int n)
{
if(n==0)
return;
printf("%5d",a);
fibonacci(b,a+b,--n);
}
Mutual recursion:
Calling two or more functions mutual is called mutual recursion. Say for example, if function A is calling B and function B is calling A recursively then it is said that, they are in mutual recursion.
Here in the following example isEvenNumber() is calling isOddNumber() and isOddNumber() is calling isEvenNumber()
#include<stdio.h>
int isOddNumber(int);
int isEvenNumber(int);
int main()
{
int n;
printf("Enter any number:");
scanf("%d",&n);
if(isEvenNumber(n))
printf("Even number");
else
printf("Odd number");
return 0;
}
int isOddNumber(int n)
{
if (0 == n)
return 0;
else
return isEvenNumber(n - 1);
}
int isEvenNumber(int n)
{
if(0 == n)
return 1;
else
return isOddNumber(n - 1);
}
Execution:
Enter any number: 15
Odd number
Execution:
Enter any number: 12
Even number
Nested recursion:
When a recursive method has a parameter defined in terms of itself then it is called nested recursion
#include<stdio.h>
int main()
{
int a,b,c,d,s;
printf("Enter four integers:\n");
scanf("%d%d%d%d",&a,&b,&c,&d);
s=sum(sum(sum(sum(a,b),c),d));
printf("Sum of four numbers %d",s);
return 0;
}
int sum(int x,int y)
{
return x+y;
}
Execution:
Enter four integers:
12 34 55 10
Sum of four numbers 121
