Why recursive function consumes more of processing time than loops?

[deanhystad]

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