Числа Фибоначчи в JS(рекурсия). Как работает функция?

Question

[Марик Цукор]

function func(n) {
  return n <= 1 ? n : func(n - 1) + func(n - 2);
}
alert(func(10)); // 55

Почему функция вернула 55? формула func(n - 1) + func(n-2) явно не формула, ведь тогда получается func(9) + func(8), а это означает, что 9 - это 34, а 8 - это 21, что в итоге дает 55, поскольку числа Фибоначчи 1(1),1(2),2(3),3(4),5(5),8(6),13(7),21(8),34(9), хотя это вы прекрасно знаете. Но вопрос в другом. Почему интерпретатор посчитал 9 за 34, а 8 за 21? это вообще не понятно, даже если учитывать, что эти данные функция берет из стека вызовов, но каким образом они туда попадают - тайный уголок для меня. Просветите, буду крайне благодарен!

Answer 1

[dadster]

Оно развертывается дальше до конца (функция рекурсивно вызывает себя), пока не получится что-то вернуть. (т.е. пока не выполнится условие n <= 1, и будет возврат n.

Для упрощения посмотрим f(5)

f(5) = f(4) + f(3) -> развертываем дальше вызовы функций с новыми параметрами, получается:
( f(3) + f(2) ) + ( f(2) + f(1) ) -> здесь для f(1) уже появляется значение (1), Но для показательности развернем все до конца:
( ( f(2) + f(1) ) + ( ( f(1) + f(0) ) + ( ( f(1) + f(0) ) + f(1), здесь уже остается только 1 вызов, для f(2), все остальные возвращают конкретные цифры, f(1) = 1, f(0) = 0. f(2) = f(1) + f(0) = 1.
Получается 1 + 1 + 1 + 0 + 1 + 0 + 1 = 5.

Такую же развертку можно сделать и для f(10), все оно тоже сведется к множеству единиц, которые сложатся в 55.

Надеюсь, вопрос состоял именно в этом, а не в механизме работы рекурсии в JS, если так, то тут я ничего не подскажу)

Answer 2

[kn1ght_t]

нарисуй на бумажке стек вызовов и поймешь

Answer 3

[Дмитрий]

сделайте улучшения ф-ции:
1. Передавайте уровень рекурсии
2. При выходе уменьшайте уровень
3. При входе увеличивайте
4. Также выводите число на данном уровне рекурсии

Будет наглядно и понятно

Comments

[Марик Цукор]

как передавать уровень функции?

[Дмитрий]

BeriaFantom: в параметре функции к примеру как-то так: func(n, level=0) { func(n, level+1)

Answer 4

[alexxandr]

погромисты школьные жыэсеры

int f(int n)
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return f(n-1) + f(n-2);
}

Answer 5

[bromzh]

Читай классику, хотя бы первые 2-3 главы, там разъясняют всё на пальцах.
Ну и посмотри на страницы 47-69.

Comments

[Марик Цукор]

я все пойму до 69 страницы? если программирование начал учить 10 дней назад, а js первый язык

Answer 6

[Alisa94]

const zero = x => x === 0 ? 0 : res(x);
const one = y => y === 1 ? y : zero(y);
const res = z => z > 1 ? res(z - 1) + res(z - 2) : one(z);