所以我对递归的概念有了相当不错的理解,但是有些实现真的让我感到震惊.以这个简单的斐波那契函数为例:
def fib(x):
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
我知道这会将斐波纳契计算分解成更小的更易处理的块.但它究竟是如何达到最终结果的呢？在递归情况下返回的确切内容是什么？看起来它只是返回一个函数调用,它将继续调用函数直到它返回1 - 但它似乎永远不会做任何真正的计算/操作.将其与经典的阶乘函数进行对比:
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n)
这里,函数显然在n上运行,每次定义一个整数,而fibonacci函数只对函数本身进行操作,直到返回1.
最后,当我们带来类似Merge Sort算法的东西时,事情变得更加怪异; 即这一段代码:
middle = int(len(L)/2)
left = sort(L[:middle], lt)
right = sort(L[middle:], lt)
print(left, right)
return merge(left, right, lt)
left和right似乎是递归调用sort,但print语句似乎表明merge正在处理每个递归调用.那么每个递归调用以某种方式"保存"然后在返回时最终调用合并时进行操作？我越来越混淆自己的第二个......我觉得我已经接近了对递归的强烈理解,但是我对递归调用的确切回复的理解正在阻碍我.
试试这个练习:
fib(0)的价值是多少？fib(1)的价值是多少？让我们把它们写下来.
fib(0) == 1
fib(1) == 1
我们知道这是因为这些是"基本情况":它匹配fib定义中的第一种情况.
好吧,让我们提一下吧.fib(2)的价值是多少？我们可以看看函数的定义,它将是:
fib(2) == fib(1) + fib(0)
我们知道fib(1)和fib(0)的价值是什么:这些都会做一些工作,然后给我们一个答案.所以我们知道fib(2)最终会给我们一个价值.
好的,搞砸了.fib(3)的价值是多少？我们可以看看定义,它将是:
fib(3) == fib(2) + fib(1)
我们已经知道fib(2)和fib(1)最终将为我们计算数字. fib(2)将比fib(1)做更多的工作,但它们最终都会触底,给我们添加的数字.
首先考虑小案例,看看当你提出问题的大小时,子问题就是我们知道如何处理的事情.
如果你已经完成了标准的高中数学课程,你将会看到类似的东西:数学家使用所谓的"数学归纳",这与我们程序员用作工具的递归是一样的.
不理解递归函数如何工作是很常见的,但它确实表明你只是不理解函数和返回是如何工作的,因为递归函数与普通函数完全相同.
print 4
这是有效的,因为该print语句知道如何打印值.它被赋予值4,并打印出来.
print 3 + 1
该print声明不了解如何打印3 + 1.3 + 1这不是一个价值,而是一种表达.幸运的是print,不需要知道如何打印表达式,因为它永远不会看到它.Python将值传递给事物,而不是表达式.所以Python所做的是在执行代码时评估表达式.在这种情况下,这会导致4产生价值.然后将值4赋给print语句,该语句可以快乐地打印出来.
def f(x):
return x + 1
print f(3)
这与上面非常相似.f(3)是表达式,而不是值.print用它做不了什么.Python必须评估表达式以产生一个值来打印.它通过查找名称来实现f,幸运的是找到了由def语句创建的函数对象,并使用参数调用该函数3.
这导致函数的主体被执行,并且被x绑定3.与在这种情况下一样print,return语句不能对表达式执行任何操作x + 1,因此Python会对该表达式求值以尝试查找值.x + 1with xbound 3生成值4,然后返回.
从函数返回值使得函数调用表达式的求值变为该值.因此,回过头来print f(3),Python已经成功地将表达式计算f(3)为值4.哪个print可以打印.
def f(x):
return x + 2
def g(y):
return f(y * 2)
print g(1)
在这里,g(2)表达式不是值,因此需要进行评估.评估g(2)将我们带到f(y * 2)了y必然1.y * 2不是一个价值,所以我们不能呼吁f它; 我们必须首先评估它,这会产生价值2.然后,我们可以调用f上2,它返回x + 2与x绑定到2.x + 2计算值4,该值从中返回f并成为表达式f(y * 2)内部的值g.这最终给出了g返回值,因此表达式g(1)被计算为值4,然后打印出来.
请注意,在向下钻取以评估f(2)Python仍然"记住"它已经处于评估的中间时g(1),一旦知道f(2)评估结果,它就会回到正确的位置.
而已.这就是全部.您不需要了解有关递归函数的任何特殊内容.return使调用此函数的特定调用的表达式成为赋予的值return.在直接表达,而不是一些更高级别的表达式称为是称为调用函数函数功能.最里面的一个.这不要紧,中间函数调用是否碰巧是相同的功能,这一个或没有.return甚至无法知道是否以递归方式调用此函数,更不用说在这两种情况下表现不同了.return 总是总是将它的值返回给这个函数的直接调用者,无论它是什么.它永远不会永远 "跳过"任何这些步骤,并将值更多地返回给调用者(例如递归函数的最外层调用者).
但是为了帮助您了解这一点,我们可以fib(3)更详细地跟踪评估.
fib(3):
3 is not equal to 0 or equal to 1
need to evaluate fib(3 - 1) + fib(3 - 2)
3 - 1 is 2
fib(2):
2 is not equal to 0 or equal to 1
need to evaluate fib(2 - 1) + fib(2 - 2)
2 - 1 is 1
fib(1):
1 is equal to 0 or equal to 1
return 1
fib(1) is 1
2 - 2 is 0
fib(0):
0 is equal to 0 or equal to 1
return 1
fib(0) is 1
so fib(2 - 1) + fib(2 - 2) is 1 + 1
fib(2) is 2
3 - 2 is 1
fib(1):
1 is equal to 0 or equal to 1
return 1
fib(1) is 1
so fib(3 - 1) + fib(3 - 2) is 2 + 1
fib(3) is 3
更简洁,fib(3)回报fib(2) + fib(1).fib(1)返回1,但fib(3)返回加上结果fib(2).fib(2)回报fib(1) + fib(0); 两者都返回1,所以将它们加在一起会fib(2)得到结果2.回到fib(3)原来fib(2) + fib(1),我们现在可以说那是2 + 1什么了3.
你失踪关键的一点是,虽然fib(0)或fib(1)回报1,那些1S型更高级别的呼叫总计达表达式的一部分.