11.8 – Types of recursion

by subbu on December 13, 2013

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

Previous post:

Next post: