<Python> Questions about executing Fibonacci sequence after implementing recursive functions

Asked 1 weeks ago, Updated 1 weeks ago, 1 views

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

python

2022-09-20 15:38

1 Answers

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


2022-09-20 15:38

If you have any answers or tips


© 2022 pinfo. All rights reserved.