Сначала n=2, затем n=0, потом снова n=2
Рекурсивные функции лучше визуализировать в виде дерева вызовов. В данном случае, это будет бинарное дерево, т.к. 1 функция (
F(n)
) может вызвать максимум 2 подфункции (
F(n - 1)
и
F(n -2)
).
Теперь самое интересное - представление в отладчике.
Вспомни, что функция заканчивается
return F(n -1) + F(n - 2)
. Ответ на твой вопрос кроется здесь.
На самом деле эта конструкция разворачивается в нечто подобное:
int prev = F(n - 1);
int prevPrev = F(n - 2);
return prev + prevPrev;
На словах:
1. Ты вызываешь корневой F(2) - n = 2
2. Дебагер заходит в функцию и опускается до
return F(n - 1) + F(n - 2)
3. Заходит в F(n - 1) - n = 1
4. Эта функция возвращает 1 - ты снова в родительской функции n = 2
5. Заходит в F(n - 2) - n = 0
6. Эта функция возвращает 1 - ты снова в родительской функции n = 2
7. Родительская (исходная) функция возвращает сумму -
1 + 1