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?
This exercise is part of the course
Practicing Coding Interview Questions in Python
Hands-on interactive exercise
Turn theory into action with one of our interactive exercises
