До сих пор каждая функция делала один рекурсивный вызов, и вызовы выстраивались в прямую цепочку. Когда функция вызывает себя два раза или больше, вызовы ветвятся, как дерево. Это одно изменение позволяет несколькими строками решать задачи, которые циклу даются трудно.
Два вызова: дерево Фибоначчи
Числа Фибоначчи начинаются с 0, 1, а каждое следующее — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13… В виде функции это два вызова:
Пройдите по шагам fib(4) и следите, как стек спускается по одной ветке,
возвращается и спускается по следующей:
fib(4): по два вызова, и одна и та же работа дважды
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int fib(int n) {
5 if (n <= 1) {
6 return n;
7 }
8 return fib(n - 1) + fib(n - 2);
9}
10
11int main() {
12 ios_base::sync_with_stdio(false);
13 cin.tie(NULL);
14
15 cout << fib(4) << "\n";
16 return 0;
17}
Начинаем в main()
строка 11Пока ничего не вызвано.
стек вызовов
main()
n—
depth0