JavaScript中的直接递归和相互递归

Question

我了解递归的基本概念，即调用自身的函数是递归。

现在我正在阅读NodeJS 文档，我发现有一些称为直接递归和相互递归的东西。我找到了一份关于相互递归的wikipedia文档。但不确定它如何与JavaScript一起使用。我对递归有以下问题。

• 函数声明和变量提升如何与相互递归配合工作？

• 直接递归是否指递归术语？

这是直接递归的一个例子吗？

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

- Laxmikant Dange

---

@rajesh 不是的，它们在顶部定义。 - Jonas Wilms

这是“直接尾递归”的一个例子 ;) - Jonas Wilms

Answer 1

1. 每次调用都会创建一个新的作用域。变量提升在所有函数上都是一样的，无论是否递归。每次调用都有自己的参数和本地变量集，因为它们在不同的堆栈帧中。然而，如果你传递对象并改变它们，那么效果将影响指向该对象的所有绑定。

2. 是的。直接递归更像数学概念。相互递归是模糊的建议，即这个函数的某个调用最终会以再次调用这个函数的实例结束，但可能存在一条漫长而复杂的路径，以至于无法通过查看代码来确定它。

3. 你的abs是直接递归。

以下是检查正数数字参数是否为奇数的示例。

直接递归：

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

相互递归：

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

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

一个函数可能在同一函数定义中同时使用直接和间接递归，然后它会执行两者。直接递归总是显式地调用自身，而间接递归则不像递归，但最终流程可以回到原始函数。这可能变得非常难以理解，编译器可能无法确定它是递归，而显式的自我调用通常很容易确定。

如果（互）递归函数处于尾部位置，则与其是否直接或互相递归无关。

- Sylwester

---

感谢您提供这么好的解释。 - Abderazak Amiar