0
Question regarding recursion
Hello, i simply cannot wrap my mind around this def fib(x): if x == 0 or x == 1: return 1 else: return fib(x-1) + fib(x-2) print(fib(4)) can anyone explain why this returns 5? The only thing i can theorise is that x is 4 and 4-1 = 3 and 4-2 = 2 and 3+2 = 5 it does however only return actual values when x is equal to 1 or 0. So from what i understand one should end up with 1 and not 5 when it has done iterating
2 Antworten
+ 1
4-1=3 and 4-2=2
Now
3-1=2 and 3-2=1 ,2-1=1 and 2-2=0
so we have 1, 1,0 now
Now 2-1=1 and 2-2=0
So it is 1,1,0,1,0 which when added together results in 5
0
recursion logic is writing a function that calls itself a number of times until a certain condition is met
x == 0 or x == 1 returns one
x is four so we will keep on decreasing its value
We first have two processes to work with: fib(3) + fib(2)
1. fib(3): # gives us two initial processes
1. fib(2): # again two initial processes
1. fib(1): 1
2. fib(0): 1 --> sum is 2
# return back to outer process
2. fib(1): returns 1 --> sum is 3
2. fib(2): # two inner processes
1.fib(1): returns 1---> sum is 4
2.fib(0): returns 1 --> sum is 5
Each process has inner processes that results in 3 + 2 = 5