# An example of mutual recursion using C

A

The first lecture of DSA was already interesting for me, I learned something about “Mutual Recursion” (when two recursive procedures call each other). The pseudo-code example was about checking if a number is either even or odd.
Given that

• 0 is even
• N is even if n-1 is odd
• N is odd if n-1 is even

And the algorithm:

```even
INPUT: n – a natural number.
OUTPUT: true if n is even; false otherwise

odd(n)
if n = 0 then return FALSE
return even(n-1)
even(n)
if n = 0 then return TRUE
else return odd(n-1)```

I implemented a tiny C program which uses it:

```int main (int argc, char const *argv[])
{
// set an integer number here
int number = 23945;
// if the number is odd (1 = TRUE)
if(odd(number)==1)
printf("%d is odd\n",number);
else
printf("%d is even\n",number);
return 0;
}

// returns 0 if the given number becomes 0, so the given number is odd
// returns even(number - 1) elsewhere
int odd(int number){
if (number==0)
return 0;
else
return even(number-1);
}

// returns 0 if the given number becomes 0, so the given number is even
// returns odd(number - 1) elsewhere
int even(int number){
if(number==0)
return 1;
else
return odd(number-1);
}
``` ##### dgraziotin

Dr. Daniel Graziotin is a senior researcher (Akademischer Rat) at the University of Stuttgart, Germany. His research interests include human, behavioral, and psychological aspects of empirical software engineering, studies of science, and open science. He is associate editor at the Journal of Open Research Software and academic editor at the Research Ideas and Outcomes (RIO) journal. Daniel was awarded an Alexander von Humboldt Fellowship for postdoctoral researchers in 2017, the European Design Award (bronze) in 2016, and the Data Journalism Award in 2015. He received his Ph.D. in computer science at the Free University of Bozen-Bolzano, Italy.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

• Norberto Mccan says:

tnanks alot

• andi says:

# define odd(n) ((n)&1)
# define even(n) (!(n&1)) or #define even(n) ((n+1)&1)

# define odd(n) ((n)%1)
# define even(n) ((n+1)%1)

what else to learn ? ..ö..
how to find a problem to an existing solution

• dgraziotin says:

Cheers for this smart example of using macros. However, the exercise was not to smartly implement the solution to the “even or odd?” problem.
The snippet was given in order to provide an example of implementation of mutual recursion in C. 