了解斐波那契数列的递归 [英] Understanding recursion with the Fibonacci Series
问题描述
我试图更好地理解递归以及return语句的工作方式.因此，我正在查看一段旨在识别与给定术语相关的斐波那契数的代码-在这种情况下为4.我很难理解else语句.
def f(n):如果n == 0:返回0如果n == 1:返回1别的:返回f(n-1)+ f(n-2)f(4) 我尝试使用Visualize Python检查每个步骤会发生什么，但是当它碰到else语句时我迷路了.
看起来它正在取n的值并减去1，以创建一个新的n值3，并返回到函数定义.因此，它似乎仅从else语句中的第一个函数返回值.但是，else语句被编写为返回2个函数f(n-1)+ f(n-2)的总和，在这种情况下，我认为返回值为5?甚至可以一起添加两个功能吗?
预先感谢您的帮助.
这里是Visualize Python中代码的链接
树流实际上与实际控制流有悖常理，但是一旦您了解了调用顺序，它就会变得更加清晰.这里要了解的是，您不断将较大的计算分解为较小的计算的总和，并在遇到基本情况( if 语句)时停止.现在，您可以执行所有的小型计算，并将这些小型计算的结果组合起来，以形成更大，更大的结果，直到获得最终答案为止.
每次递归调用命中基本情况时，它都会根据命中的大小写返回1或0.该值将返回给前一个调用者.要了解，请考虑:
f(1) 3 + f(0) 3 请注意，下标表示递归调用树的深度.调用由 f(2) 2 进行.首先计算 f(1) 3 ，然后将 1 返回到 f(2) 2 .然后计算 f(0) 3 ，然后将 0 返回到 f(2) 2 .将两个返回值相加，结果为 1 .
f(2) 2 ，然后将 1 返回给称为 it 的人，在这种情况下恰好是 f(3) 1 . f(3) 1 称为 f(2) 2 + f(1) 2 ，与此同时，另一个 f(1) 2 也将 1 返回给 f(3) 1 ，他现在将其与 f(2) 2 的结果相加，形成 2 .
f(3) 1 现在将 2 传递给 f(4) 0 恰巧调用了 f(3) 1 + f(2) 1 ...
查看此问题的另一种方法是从实际进行的第一个函数调用开始: f(4) 0 .
f(4) 0 计算 f(3) 1 + f(2) 1 .但是要计算 f(3) 1 ，需要知道 f(2) 2 + f(1)2 ，类似地，要计算 f(2) 1 ，则需要知道 f(1) 2 + f(0) 2 ，依此类推.
I am trying to better understand recursion and how return statements work. As such, I'm looking at a piece of code meant to identify the fibonacci number associated with a given term -- in this case, 4. I'm have difficulty understanding the else statement.
def f(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return f(n-1) + f(n-2)
f(4)
I have tried using Visualize Python to examine what happens at each step, but I get lost when it hits the else statement.
It looks like it is taking the value of n and subtracting 1, to create a new n value of 3 which it returns to the function definition. So it appears to only be returning the value from the first function in the else statement. However, the else statement is written to return the sum of 2 functions f(n-1) + f(n-2), in which case I thought the return value would be 5? Can you even add 2 functions together?
Thanks in advance for your help.
Here is a link to the code in Visualize Python Sum of 2 functions
When in doubt, just break it down.
The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you hit the base case (the if statements). Now you can carry out all the small computations, and combining the results of those small computations to form a bigger, larger result, until you have your final answer.
Every time a recursive call hits the base case, it will return either 1, or 0, depending on what case was hit. This value will be returned to the previous caller. To understand, consider:
f(1)3 + f(0)3Note here that the subscript represents the depth of the recursion call tree. The call is made by f(2)2. f(1)3 is computed first, and 1 is returned to f(2)2. f(0)3 is then computed, and 0 is returned to f(2)2. The two return values are summed, and the result is 1.
f(2)2 then returns 1 to whoever called it, which in this case happens to be f(3)1. f(3)1 called f(2)2 + f(1)2, meanwhile this other f(1)2 also returns 1 to f(3)1, who now adds that with the result of f(2)2, to form 2.
f(3)1 now passes 2 to f(4)0, its caller, which happened to call f(3)1 + f(2)1 ... and so it goes.
An alternative way of looking at this is to start from the first function call that is actually made: f(4)0.
f(4)0 computes f(3)1 + f(2)1. But to compute f(3)1, it needs to know f(2)2 + f(1)2, and similarly, to compute f(2)1, it needs to know f(1)2 + f(0)2, and so on.
这篇关于了解斐波那契数列的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
