Direct and Mutual Recursion in JavaScript

Question

I am aware of basic concept of recursion, i.e. A function which calls itself is recursion.

Now I was going through NodeJS documentation, I found something called Direct Recursion and Mutual Recursion. I found a wikipedia documentation regarding Mutual recursion. But not sure how it works with JavaScript. I have following questions about recursion.

• How does Function declaration and variable hoisting work with mutual recursion?

• Does direct recursion refer to term recursion?

Is this an example of direct recursion?:

function abc(num,sum){
   if(num<=0) return sum;
   return abc(--num,sum);
}

Answer 1

1. Each call makes a new scope. Variable hoisting works the same on all functions regardless if it's recursion or not. Each call has their own set of the argument and local variables since they are in different stack frames. However if you pass objects and mutate them then the effect will be for all bindings that point to that object.

2. Yes. Direct recursion is more like the mathematical concept. Mutual recursion is vague suggestion that somewhere a call from this function will eventually end up with a call to an instance of this function again, but there might be a long and complex path such that it might not be possible to determine it by looking at the code.

3. Your abs is direct recursion.

Here are examples that checks if a positive numeric argument is odd.

Direct recursion:

function isOddDirect(n) {
  if (n < 1)
    return false;
  if (n === 1)
    return true;
  return isOddDirect(n-2);
}

Mutual recursion:

function isOdd(num) {
  if (num === 1)
    return true;
  return !isEven(num-1);
}

function isEven(num) {
  if (num === 0)
    return true;
  return !isOdd(num-1);
} 

A function might use both direct and indirect recursion in the same function definition and then it would do both. Direct is always that it calls itself explicitly while indirect is where it doesn't look like recursion but eventually flow can lead back to the original function. It's possible to make this so obscure that the compiler wouldn't know it is recursion while a explicit self call usually are easy to determine.

If the (mutual) recusive function is in tail position has nothing to do if it is direct or mutual.