Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's the term for "double recursion"?

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?

like image 855
Dan Tao Avatar asked Jan 03 '11 17:01

Dan Tao


2 Answers

It's called mutual recursion.

like image 149
Jon Purdy Avatar answered Sep 28 '22 01:09

Jon Purdy


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.

like image 34
Blaise Pascal Avatar answered Sep 27 '22 23:09

Blaise Pascal