Каков лог c порядка звонков, в рекурсии в Javascript?

Question

Мне трудно понять порядок вызовов в рекурсивном программировании в Javascript

Играя с рекурсивным программированием в Javascript, я хотел найти решение для случая использования Фибоначчи. Фибоначчи - это всего лишь пример использования, чтобы проиллюстрировать мой вопрос. Но вопрос о рекурсивном программировании в JS, а не об алгоритме Фибоначчи.

Учитывая номер индекса 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() в мой код. И вот тогда произошло потрясение ума. *

Порядок звонков, счетчик и шаги не имеют для меня никакого смысла!

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

Другой способ визуализировать это, добавив другой вид ведения журнала, чем ваш 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

Из этого видно, что мы продолжайте выполнять левые вызовы (первый рекурсивный шаг) до того, как мы вернемся на уровень и выполним правые, вернемся на другой уровень и выполним его правые, и т. д. c.

Вы можете видеть, как я добавил запись в этом фрагменте:

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}

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