共计 1956 个字符，预计需要花费 5 分钟才能阅读完成。
递归是个有意思的概念，正如在前面所说，递归能让算法的可读性大大提高，而且通常要比使用循环结构更能写出准确的算法。这本书形象引入了递归，并没有太深入，所以我进行了一点“添油加醋”。
递归
概念
递归其实就是自己调用自己。可以从多种维度对递归分类，我见过的最常见的分类：
直接递归
自己直接调用自己。如：
–haskell
length’ :: [a] -> Int
length’ [] = 0
length’ (_:xs) = 1 + length’ xs
上面定义的 length’ 就是通过直接递调用自身完成列表长度的计算。
间接递归
可以认为只要不是直接调用自己的递归都是间接递归，其表现形式较多，如 A ->（调用）B，B->（调用）A，如奇偶谓词函数：
–haskell
odd’ :: Int -> Bool
odd’ 0 = False
odd’ n = even’ (n – 1)
even’ :: Int -> Bool
even’ 0 = True
even’ n = odd’ (n – 1)
也可以有 A ->B，B->C，… Z->A。这里就不举例子了。
书中的例子
有一个盒子，盒子里套着一个或多个盒子，盒子里的盒子又有盒子，依次类推。而钥匙就在某个盒子里，我们怎么找到钥匙呢。
策略一
伪代码如下：[伪代码是对手头问题的简要描述, 看着像代码, 但其实更接近自然语言。]
def look_for_key(main_box):
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
box = pile.grab_a_box()
for item in box:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print “found the key!”
如果学习过树的遍历，是不是发现这就是广度优先遍历啊
策略二
伪代码如下：
def look_for_key(box):
for item in box:
if item.is_a_box():
look_for_key(item)
elif item.is_a_key():
print “found the key!”
对应的就是深度优先遍历啊
这两种方法的作用相同, 但第二种方法更清晰。递归只是让解决方案更清晰, 并没有性能上的优势。实际上, 在有些情况下, 使用循环的性能更好。Leigh Caldwell 在 Stack Overflow 上说的一句话:“如果使用循环, 程序的性能可能更高; 如果使用递归, 程序可能更容易理解。如何选择要看什么对你来说更重要。”
基线条件和递归条件
每个递归函数都有两部分: 基线条件 (base case) 和递归条件(recursive case)。递归条件指的是函数调用自己, 而基线条件则指的是函数不再调用自己, 从而避免形成无限循环。递归条件一定是向基线条件靠拢的，否则，只能无限递归下去。如
#python
def countdown(i):
print i
if i <= 0:
return
else:
countdown(i-1)
上述函数中 i 的值收敛于 0，即达到基线条件，从而不会无限递归下去。
栈
主要讲了与递归相关的一种数据结构 – 栈（stack）。栈是一种支持 FILO（First In Last Out）的数据结构。为什么要提这种数据结构呢？
调用栈
这是因为现代计算机对函数的实现用到了调用栈（call stack）的栈。调用函数时，计算机将首先为该函数调用分配一块内存。每当你调用函数时, 计算机都将函数调用涉及的所有变量的值存储到内存中。
假设 A 函数调用 B 函数，此时计算机为两个函数分配了内存，暂且称之为 A 函数内存和 B 函数内存，它们的位置关系如下：—- 栈顶 —- B 函数内存—————A 函数内存—————
若 B 函数执行完，计算机就可以回收 B 函数内存了，即从栈顶弹出 B 函数内存，此时只有 A 函数内存了。—- 栈顶 —- A 函数内存—————
以上操作符合 FILO 的定义，调用栈是栈的一种具体应用。
那如果调用栈数量太多，会有什么后果呢？
递归调用栈
#python
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
对于较小的正整数，这个程序没有问题；而如果 x 较大，在 fact 执行的时会发现内存量会飙升，甚至会出现程序无法正常执行下去。这是因为此时递归调用栈的情况类似：—- 栈顶 —-fact(1)函数内存———————…———————fact(n-2)函数内存———————fact(n-1)函数内存———————fact(n)函数内存———————
fact(n)依赖 fact(n-1)，依次类推，导致计算机存储了大量函数调用的信息。这类问题大体有两种解决方式：
重新编写代码, 转而使用循环。
使用尾递归。现在已经有很多编译器支持尾递归优化了。
我的公众号地址
