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..!!

One character for 95 numbers..

Hi guys...
this is my very first blog.....
I was thinking about what to start with..when my eyes fell on a post in the computer programming group of our clg BESU on fb...where one of my seniors posted a problem regarding storing of large values...like 100! or 4^1000000 etc...
i was thinking how to represent such a large data in a single variable....
when i came through Data structures....i read a book n i realized tht linked list(as u all must be quite familiar with)...can be used to represent it.....
like we can represent a large no lik 987654321 in a doubly linked list as : -
9=8=7=6=5=4=3=2=1
where '=' represents a double linked....
n the structure shud be
struct digit
{
int data;
struct digit* prev;
struct digit* next;
}
so this is the one which i have seen...so far...!!

but i got a diff idea....!
i would like to represent in the same way bt  each digit wud be represented with a char rather than an int...!!
the structure wud be : -
struct digit
{
char data;
struct digit* prev;
struct digit* next;
}

seems same as the previous one...??isnt it...??
bt my dear...its not....
in a normal char/int array it wil store '0'-'9' / 0-32768(for 2 bytes)....
the first case wud be the normal n expected one...
whereas the second one is ok....

bt i have got a diff approach...
i thot that the char data wud store ascii characters n their corresponding ascii codes will store our required number....
ok....lets elaborate....

                                                  TABLE 1-a

 ok so above u can see the most famous ascii table...
if u can observe properly the leftmost column (ascii codes)then you will realize that the ascii characters wid codes from 0-31...cannot be input using the keyboard....
but from ascii code 32...ie its corresponding ascii character - ' ' (space) can be input using keyboard....
and aftr 32 we can input characters from keyboard till ascii codes 126.....ie its ascii char '~' .....

now like hexadecimal whr 0 represnts 0 ......til 'A' represents 10......'F' represents 15....
similarly in my new  ALPHANUMERIC NUMBER SYSTEM i want to represent
0 wid 32 s ascii char ie  '  '
1 wid 33 s ascii char ie  '!'
2 wid 34 s ascii char ie  '"'
3 wid 35 s ascii char ie '#'
n so on....
till
94 wid 126 s ascii char ie '~'
the part of ascii table we ll consider is :-

                                                                  TABLE  1-b

n  this is way we can represent (126-32)+1= 95 characters wid jst 1 character....
so the number will start like this:-

                                                                TABLE 1-c
so the structure to represent the digit will be-
struct digit
{
char data;
digit* prev;
digit* next;
}
in this blog we will consider only  a single character number....ie (from 0-94)
multi character numbers  will be taken care of in future blogs...
ok so if d user is asked for entering a number in the new alphanumeric form...
he can enter in form of a string/char... n we will output its corresponding no(from table 1-c) as -  
input - A
output - 33

so guys...i hope you liked my idea...
in later blogs i ll discuss about the
simple arithmetic operations
storage of this alphanumeric data..
thank u..!!
Njy Lyf :)
Keep Rocking...!!