Как работает эта функция?

Question

[almata81]

function fib(num) {
      if (num <= 2)
        return 1;
      return fib(num - 1) + fib(num - 2);
    }
  document.write(fib(6));

Comments

[Сергей Горностаев]

Обычная рекурсивная функция. Тег "Функциональное программирование" тут не при чём.

Answer 1

[Dmitry Tyvaniuk]

Медленно :)
Сложность выходит O(n^2)
Считайте числа Фибоначчи так (сложность O(n) и без рекурсии):

const fib = (n) => {
    const buf = [0, 1];
    for (let i = 2; i <= n; i++) {
        buf[i % 2] += buf[(i + 1) % 2];
    }
    return buf[n % 2];
};

Comments

[almata81]

спасибо

Answer 2

[Developer]

Это вычисление чисел Фибоначчи из любой книги по программированию для начинающих для демонстрации как работает рекурсия.
В чём прикол? Про числа Фибоначчи все знают

Comments

[almata81]

спасибо за ответы. Рекурсию я знаю давно но, про чисел Фибоначчи узнал только что прочитав интернет, но любом случае ваши ответы помогли узнать ответы моих вопросов