Mutual Recursion

Hi guys in this post I will talk about recursion.

WHAT WE KNOW :

As we know a function is said to be recursive if it calls itself.
For eg -
a()
{
   // statements
a();
//statements
}

since a() calls itself,it is a recursive function.

In our programming lives,we always encounter recursion in terms of sorting,searching,and many more.
But in such recursions,there is usually one single recursive function.
ie.
a()
{
b();//where b is a non recursive function.
a();
}
b()
{
//statements but NO FUNCTION TO b() or a()
This is usually the case of mergesort and quicksort.

MUTUAL RECURSION :

But I am going to talk about a different type of recursion where a() calls b(),then b() calls a() and so on.
This is the case where usually a problem is subdivided into 2 or more parts recursively,to simplify and solve the problem in a lesser time complexity. 

Syntax :

For 2 mutually recursive functions
a()
{
//statements
b();
}
b()
{
//statements
a();
}
So as we can see this is a MUTUAL RECURSION,where both a() and b() are dependent on each other for recursive calls.

Example :

So lets see an application of this type of recursion
Find the sum of the series -
(((1+2)*3 +4)*5 +6)*7 +8.....n
Input   8
Output  505
Input 5
Output 65

So here's C the code using MUTUAL RECURSION
1   #include<stdio.h>
2   int sum(int);
3   int prod(int);
4   main()
5   {
6   int n,ans;
7   scanf("%d",&n);
8   if(n%2==1)
9       ans=prod(n);
10 else ans = sum(n);
11 printf("%d",ans);
12 return 0;
13 }
14 int prod(int n)
15 {
16 if(n==1)
17 return 1;
18 return n*sum(n-1);
19 }
20 int sum(int n)
21 {
22 return n+prod(n-1);
23 }
In this simple code, I have broken the calcultaion of series into  2 parts - summation(done by sum())  and the multiplication (done by prod())
Lets analyse the problem with input n = 5
since n is odd prod(5) is called.
n(5) not equal to 1,so return 5*sum(4) occurs
sum(4) is called
return 4+prod(3) occurs
prod(3)is called
n(3) not equal to 1,so return 3*sum(2) occurs
sum(2) is called
return 2+prod(1) occurs
n(1) is equal to 1,so return 1


5*sum(4) = 5*( 4+prod(3)) =5*( 4+3*sum(2)) = 5*( 4+3*(2+prod(1)))= 5*( 4+3*(2+1)))
so we got the series... (((1+2)*3 +4)*5 using the recursion
so we obtain the final result as 65

APPLICATIONS :

We can use this type of recursion in problems,where we need to perform 2 or more operations recursively.
For eg - In the above example we performed summation and multiplication recursively.
This type of recursion may sound complex,but it usually simplifies a complicated problem by breaking it up into 2 or more smaller parts.

Thank you.
Enjoy Life :)
Keep Rocking..!!