Python (code implemented using the Fibonacci sequence recursive function)
def fib(n):
if n ==1 or n==2:
return 1
return fib(n-1)+fib(n-2)
print(fib(6))
If you execute the above code, the return value becomes fib(5)+fib(4) after 6 is assigned to n because of print(fib(6)), and then how is 5 assigned to n?
Below is a list of what I think is the execution process. If there is any mistake, please correct it.
1.fib(6) = fib(5)+fib(4)
2.fib(5) = fib(4)+fib(3)
3.fib(4) = fib(3)+fib(2)
4.fib(3) = fib(2)+fib(1)
5.fib(2) = 1
6.fib(1) = 1
7.fib(3) = 2
8.fib(2) = 1
9.fib(4) = 3
10.fib(3) = fib(2)+fib(1)
11.fib(2) = 1
12.fib(1) = 1
13.fib(3) = 2
14.fib(5) = 5
15.fib(4) = fib(3)+fib(2)
16.fib(3) = fib(2)+fib(1)
17.fib(2) = 1
18.fib(1) = 1
20.fib(3) = 2
21.fib(2) = 1
22.fib(4) = 3
23.fib(6) = 8
That's roughly right.
To be more clear, you can leave a logging and check it. This is the logging code created by the decorator below, and it is the result.
def log_recurse(f, l=[0]):
def g(*arg, **kwarg):
print(">>" * l[0], *arg)
l[0] += 1
r = f(*arg, **kwarg)
l[0] -= 1
print("<<" * l[0], *arg)
return r
return g
@log_recurse
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)
print(fib(6))
6
>> 5
>>>> 4
>>>>>> 3
>>>>>>>> 2
<<<<<<<< 2
>>>>>>>> 1
<<<<<<<< 1
<<<<<< 3
>>>>>> 2
<<<<<< 2
<<<< 4
>>>> 3
>>>>>> 2
<<<<<< 2
>>>>>> 1
<<<<<< 1
<<<< 3
<< 5
>> 4
>>>> 3
>>>>>> 2
<<<<<< 2
>>>>>> 1
<<<<<< 1
<<<< 3
>>>> 2
<<<< 2
<< 4
6
8
© 2024 OneMinuteCode. All rights reserved.