I have the following exercise:
"Write a recursive function that prints the n-th number of the fibonacci sequence. The function parameters are 'n','current_number' [F(0)] and 'next_number' [F(1)]. [F(0)] and [F(1)] are the initial seeds of the sequence. Write the main program that ask user for the input parameters. Your code must output the result as follows.
fibon({n},{current_number},{next_number}) = {result}
fibon(5,4,5) = 37
fibon(5,0,1) = 5
fibon(10,0,1) = 55
The following solution seems to work
def fibon(n, current_number, next_number):
#print(f'n is {n} from the outset')
if n == 0:
#print('n == 0 is true')
return current_number
elif n == 1:
#print('n == 1 is true')
return next_number
else:
n = n-1
#print(f'this is n-1 {fibon(n-1, current_number, next_number)}')
#print(f'this is n {fibon(n, current_number, next_number)}')
fib= fibon(n-1, current_number, next_number) + fibon(n, current_number, next_number)
#print(fib)
return(fib)
However, I don't understand how 'fibon' is returning the value of nth number in fibonacci series. It is a recursive function and I don't understand how every time it loops, it gets the fibonacci number for the nth position. If you look at the code, " fibon(n-1, current_number, next_number) + fibon(n, current_number, next_number)" can only return a number when n== 1 or n==0. If so, how it can reutrn other numbers in the position when they are not in the 1th or 0 position?
I am not sure if I made a lot of sense but I tried to express my confusin. Thanks in advance!
The code is working but I do not seem to understand why it is working. You can also propose a better solution if there is one. Thank you very much!
O(2ⁿ)
, where an iterative solution isO(n)
). 2) Python in particular is a bad language for recursion; the reference interpreter, and probably others, can't do tail call optimization, and set a relatively low bound for recursion depth. If the call stack exceeds that limit, you die with aRecursionError
.sys.getrecursionlimit() * 2
(the multiplier being due to how your recursion is currently structured; the limit is typically on the order of 1000-3000, depending on build settings and tweaks by third-party tools like IPython), which will die immediately due to excessive recursion in the initial linear path down tofib(0)
.