调用顺序的逻辑，以Java语言（Fibonacci用例）递归吗？

Question

我很难理解Java递归编程中的调用顺序

[在尝试使用Java进行递归编程时，我想找到针对Fibonacci用例的解决方案。

给出索引号N，返回斐波那契数列的相应值，其中该数列为：1、1、2、3、5、8、13、21、34、55、89、144，...） 。

我使用以下解决方案（我知道我可以通过记忆来改进它以避免指数复杂性）：

function fibonacci(n) {
  if (n <= 1) return 1;
  return fibonacci(n-1) + fibonacci(n-2);
}

---

为了更好地理解它，我开始在代码中添加console.log()。就是在那时候发生了f俩。]

调用顺序，枚举器和步骤对我来说没有任何意义！

function fibonacci(n, caller = 'initalFibonacciCaller', step = 0) {
  console.log(caller)
  console.log('n =', n)
  console.log('step =', step)
  console.log('----------------')

  if (n <= 1) return 1;
  step++
  return fibonacci(n-1, 'fibonacciCaller1', step) + fibonacci(n-2, 'fibonacciCaller2', step);
}

console.log('=>', fibonacci(4))

响应：

initalFibonacciCaller
n = 4
step = 0
----------------
fibonacciCaller1
n = 3
step = 1
----------------
fibonacciCaller1
n = 2
step = 2
----------------
fibonacciCaller1
n = 1
step = 3
----------------
fibonacciCaller2
n = 0
step = 3
----------------
fibonacciCaller2
n = 1
step = 2
----------------
fibonacciCaller2
n = 2
step = 1
----------------
fibonacciCaller1
n = 1
step = 2
----------------
fibonacciCaller2
n = 0
step = 2
----------------

5

[从step3 fibonacciCaller2开始，n开始增加而steps开始减少？这可能是由于我对Javascript的工作原理缺乏了解，但是我希望对此做一个很好的解释。

Answer 1

斐波那契数的顺序由公式Fn = Fn-1 + Fn-2确定。也就是说，下一个数字是前两个数字的和。

前两个数字是1，然后是2（1 +1），然后是3（1 + 2），5（2 + 3），依此类推：1、1、2、3、5、8、13、21 ...，

斐波纳契数根据定义是递归的：

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

对于较大的n值，这样的解决方案将在很长的时间内起作用。例如，fib（77）可以使浏览器挂起一段时间，从而耗尽所有处理器资源。

这是因为该函数产生大量的嵌套调用树。在这种情况下，一遍又一遍地多次计算出一系列值。

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

这里可以看出，fib（5）和fib（4）同时需要fib（3）的值。它将完全独立地计算两次。

您可能会注意到fib（3）被计算两次，而fib（2）被计算三次。计算总数的增长速度远远快于n，即使对于n = 77，这也非常庞大。

完整的递归树：

Answer 2

您可以采用另一种方法，并通过添加尖括号作为步骤来可视化递归的一侧，并获得一侧的调用顺序。

例如，递归首先全部到达分叉的左侧，然后最后一步到达右侧。

function fibonacci(n, step = { s: 0 }, sides = '') {
    console.log(++step.s, n, sides);
    if (n <= 1) return 1;
    return fibonacci(n - 1, step, sides + '< ') + fibonacci(n - 2, step, sides + '> ');
}

console.log(fibonacci(5));

.as-console-wrapper { max-height: 100% !important; top: 0; }