13

Here's an obviously recursive function:

function()
{
    function();
}

We would simply call this "recursive"—but what about this (barely) more complex version?

functionLeft()
{
    functionRight();
}

functionRight()
{
    functionLeft();
}

Is there a term for this scenario, e.g., "double recursion"? Or is there no specific term to distinguish this case from the single-function case above?

3 Answers 3

27

It's called mutual recursion.

0
16

As Jon Purdy said, the example you gave is called "mutual recursion". The term "double recursion" also exists, but with a different meaning: for when a function uses two recursive calls. The classic example is the Fibonacci function"

int Fib(int n)
{
  if (n < 2) return 1;
  return Fib(n-1) + Fib(n-2);
}

The Fib(n) function recursively calls itself twice.

2
  • Note that this is a crazy-inefficient way to compute fibonacci numbers (because you do the same computation many times)
    – amindfv
    Sep 25, 2012 at 22:40
  • True, but it was the first, and simplest, double recursion example I could think of. I suppose I could have shown QuickSort, but that's a bit more complicated. Oct 29, 2012 at 18:06
1

One interpertaion of double recursion could be divide and conquer (e.g) quicksort

quicksort = quicksort smaller ++ pivot ++ quicksort larger

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.