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);
}

About the author

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.

3 comments

Leave a Reply to Norberto Mccan Cancel reply

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

  • # 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

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

About Author

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.