Starting with a really simple case:
fib[4] = fib[3] + fib[2]
fib[4] = (fib[3] = fib[2] + fib[1]) + (fib[2] = fib[1] + fib[0])
fib[4] = (fib[3] = (fib[2] = fib[1] + fib[0]) + fib[1]) + (fib[2] = fib[1] + fib[0])
That's 9 calls to fib().
This code records the number of times fib[n] is called for each value of n:
calls = {}
def fib(n):
calls[n] = calls.get(n, 0) + 1
if n < 2:
return 1
else:
return fib(n-1) + fib(n-2)
fib(5)
for n, count in calls.items():
print(f'{n:3d} : {count:5d}')
print('Total', sum(calls.values()))
Output:
5 : 1
4 : 1
3 : 2
2 : 3
1 : 5
0 : 3
Total 15
Just doubling starting n from 5 to 10 does this:
Output:
10 : 1
9 : 1
8 : 2
7 : 3
6 : 5
5 : 8
4 : 13
3 : 21
2 : 34
1 : 55
0 : 34
Total 177
And this is the horrible thing that happens when n = 40
Output:
40 : 1
39 : 1
38 : 2
37 : 3
36 : 5
35 : 8
34 : 13
33 : 21
32 : 34
31 : 55
30 : 89
29 : 144
28 : 233
27 : 377
26 : 610
25 : 987
24 : 1597
23 : 2584
22 : 4181
21 : 6765
20 : 10946
19 : 17711
18 : 28657
17 : 46368
16 : 75025
15 : 121393
14 : 196418
13 : 317811
12 : 514229
11 : 832040
10 : 1346269
9 : 2178309
8 : 3524578
7 : 5702887
6 : 9227465
5 : 14930352
4 : 24157817
3 : 39088169
2 : 63245986
1 : 102334155
0 : 63245986
Total 331160281