Javascript 中的递归调用顺序的逻辑是什么？

Question

我很难理解 Javascript

中递归编程的调用顺序

在 Javascript 中尝试递归编程时，我想为 Fibonacci 用例找到一个解决方案。斐波那契只是一个用例来说明我的问题。但是问题是关于JS中的递归编程，而不是关于斐波那契算法。

Given an index number N, return the corresponding value of the Fibonacci sequence, where the sequence is: 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() 。那就是他妈的发生的时候。

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

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

为什么从step3fibonacciCaller2开始，n开始增加，steps开始减少？
这可能是由于我对 Javascript 的工作原理缺乏了解，但我希望对此有一个很好的解释。

Answer 1

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

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

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; }

Answer 2

另一种可视化方式，通过添加与 steps 不同的日志记录方式，使用缩进参数代替，得到如下结果：

fibonacci (4)
    left:
        fibonacci (3)
            left:
                fibonacci (2)
                    left:
                        fibonacci (1)
                        ==> 1    -- fibonacci (1) (base case)
                    right:
                        fibonacci (0)
                        ==> 1    -- fibonacci (0) (base case)
                ==> 1 + 1 ==> 2    -- fibonacci (2)
            right:
                fibonacci (1)
                ==> 1    -- fibonacci (1) (base case)
        ==> 2 + 1 ==> 3    -- fibonacci (3)
    right:
        fibonacci (2)
            left:
                fibonacci (1)
                ==> 1    -- fibonacci (1) (base case)
            right:
                fibonacci (0)
                ==> 1    -- fibonacci (0) (base case)
        ==> 1 + 1 ==> 2    -- fibonacci (2)
==> 3 + 2 ==> 5    -- fibonacci (4)

Returning 5

从这里可以看出，我们一直在进行左侧调用（第一个递归步骤），然后再返回一个级别并执行右侧的调用，返回另一个级别并执行其右侧-手等

您可以在这段代码中看到我是如何添加日志记录的：

const log = (indent, message) => 
  console.log (Array(indent * 2).fill('  ').join('') + message)

function fibonacci(n, indent = 0) {
  log (indent, `fibonacci (${n})`)
  if (n <= 1) {
    log(indent, `==> 1    -- fibonacci (${n}) (base case)`)
    return 1;
  }
  log (indent + 1, 'left:')
  const left = fibonacci(n-1, indent + 2) 
  log (indent + 1, 'right:')
  const right = fibonacci(n-2, indent + 2)
  const result = left + right;
  log(indent, `==> ${left} + ${right} ==> ${result}    -- fibonacci (${n})`)
  return result
}

console .log (``, `Returning ${fibonacci(4)}`)

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

Javascript 中的递归调用顺序的逻辑是什么？

What is the logic of the order of the calls, in recursion in Javascript?

javascript

recursion

fibonacci

我很难理解 Javascript