an example of mutual recursion using c

2011-04-10

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

I do not use a commenting system anymore, but I would be glad to read your feedback. Feel free to contact me.