Może poniższy szkic funkcji skuteczniej przekaże idea rozwiązania. Docelowo f(k//2)
to jedyne wywołanie rekurencyjne:
def f(k):
"""f(k) = fib(k), fib(k+1)"""
if k == 0:
return 0, 1
a, b = f(k // 2)
if k % 2 == 0:
# k = 2n
# a = fib(n)
# b = fib(n+1)
# return fib(2n), fib(2n+1)
else:
# k = 2n+1
# a = fib(n)
# b = fib(n+1)
# return fib(2n+1), fib(2n+2)