Calculate the number of function calls

Let's consider a classic example of recursion – the Fibonacci sequence, represented by non-negative integers starting from 0 with each element \(F(n)\) equals the sum of the preceding two: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... You are given a function that returns a tuple with the \(n\)-th element of the sequence and the amount of calls to fib() used:

def fib(n):

  if n < 2:
    return (n, 1)

  fib1 = fib(n-1)
  fib2 = fib(n-2)

  return (fib1[0] + fib2[0], fib1[1] + fib2[1] + 1)

How many calls to fib() are needed to calculate the \(15^{th}\) and \(20^{th}\) elements of the sequence?

Possible answers

\(15^{th}\) element: 3193 calls; \(20^{th}\) element: 35421 calls

\(15^{th}\) element: 1973 calls; \(20^{th}\) element: 21891 calls

\(15^{th}\) element: 3193 calls; \(20^{th}\) element: 21891 calls

\(15^{th}\) element: 35421 calls; \(20^{th}\) element: 1973 calls

Exercise

Calculate the number of function calls

Instructions

Possible answers