所以我对递归的概念有相当不错的理解，但有些实现确实让我感到困惑。以这个简单的斐波那契函数为例:
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，一个定义的整数进行操作，而斐波那契函数只对函数本身进行操作，直到返回 1。
最后，当我们使用诸如合并排序算法之类的东西时，事情会变得更加奇怪；即这块代码:
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，但打印语句似乎表明 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) 做更多的工作，但它们最终都会触底反弹给我们可以相加的数字。
先处理小案例，看看当你增加问题的规模时，子问题是我们将知道如何处理的事情。
如果你上过标准的高中数学课，你就会看到类似的东西:数学家使用所谓的“数学归纳法”，这与我们程序员用作工具的递归相同。
