Здесь есть много хороших ответов, но я сделал эту диаграмму, которая помогает лучше объяснить результат функции.Единственные значения, которые когда-либо будут возвращены, это 1 или 0 (ваш пример возвращает 1 для n <2, но вместо этого должен возвращать n). </p>
Это означает, что каждый рекурсивный вызов в конечном итоге будет возвращать либо 0, либо1. В итоге они «кэшируются» в стеке и «переносятся» в исходный вызов и складываются вместе.
Так что, если бы вы нарисовали эту же диаграмму для каждого значения 'n', вы могли бынайдите ответ вручную.
Эта диаграмма приблизительно показывает, как каждая функция возвращается для fib (5).
Это показываетпоток управления, т.е. порядок выполнения функций.Помните, что код всегда выполняется слева-> справа и сверху-> снизу.Поэтому всякий раз, когда вызывается новая функция, она приостанавливается, и затем происходит следующий вызов.
Ниже приведен фактический поток управления, основанный на исходном сообщении.Обратите внимание, что базовое условие if (n <= 0) {return 0} else if (n <= 2) {return 1;} для упрощения:
1. fib(5) {
return fib(4) + fib(3);
2. fib(4) {
return fib(3) + fib(2);
3. fib(3) {
return fib(2) + fib(1);
4. fib(2) {
A= return 1;
};
5. fib(1) {
B= return 1;
};
C= return 2; // (1 + 1)
};
6. fib(2) {
D= return 1;
};
E= return 3; // (2 + 1)
};
7. fib(3) {
return fib(2) + fib(1);
8. fib(2) {
F= return 1;
};
9. fib(1) {
G= return 1;
};
H= return 2; // (1 + 1)
};
I= return 5; // (3 + 2)
};