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

4th Jun 2020, 11:05 AM
Simon Hylleberg
Simon Hylleberg - avatar
2 Respuestas
+ 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
4th Jun 2020, 11:29 AM
Abhay
Abhay - avatar
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
4th Jun 2020, 12:14 PM
Ali Abdelhady
Ali Abdelhady - avatar