递归

引言

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

概念

递归指在函数的定义中使用函数自身的方法。指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

日常事例

• 查字典
• 阅读维基百科（内链）

图示

特点

• 方法里调用自身。
• 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
• 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
• 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

表现在 Python 语言中，即为报错信息RecursionError: maximum recursion depth exceeded in comparison. 默认递归深度为 1000 ，我们可以通过修改下面的代码设置调节，但是通常不建议这样操作。（效率太低）

import sys
sys.setrecursionlimit(100000)

伪代码比较迭代和递归

我们通过一个在大箱子中找钥匙的场景来对迭代和递归进行比较。(参照算法图解)

def look_for_key_with_iteration(big_box):
    pile = big_box.make_a_pile_to_look_through()        # 把大箱子里面的东西一股脑倒出来
    while pile.is_not_empty():      # 在堆里开始查找
        box = pile.grap_a_box()     # 拿起大箱子中的一个物品
        for item in box:            
            if item.is_box():       # 如果是盒子
                pile.append(item)   # 收集到盒子堆里，等待后续可能的进一步查找
            elif item.is_key():     # 如果是钥匙，说明找到了
                return 'found key'


def look_for_key_with_recursion(big_box):
    for item in big_box:
        if item.is_box():
            look_for_key_with_recursion(item)       # 如果拿到的是盒子，把这个盒子先翻个底朝天
        elif item.is_key():                         # 如果拿到钥匙，则大功告成
            return 'found key'

如果使用循环，程序的性能可能更好；如果使用递归，程序可能更容易（被程序员）理解。如何选择要看你更看重选择。参见此处

代码

见此处

尾递归

在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。

def bar():
    pass
    
def foo():
    return bar()

上面代码中，函数foo()的最后一步是调用函数bar()，这就叫尾调用。 具体实现见代码中的tail_recursion_fact()函数。

Python解释器没有做优化，所以，即使把上面的factorial(n)函数改成尾递归方式的tail_recursion_fact()，也会导致栈溢出。

通过特殊的装饰器，我们也可以实现Python开启尾递归优化,详见代码中的tail_call_optimized()函数。

注意

尽管使用递归思想编写程序通常可以使条理更加清晰，但是有可能导致消耗的空间和时间使我们得不偿失。 比如fib_normal()、fib_recursion()和fib_tail_recursion()在计算Fibonacci数列前30项时，消耗的时间分别是:

The function **fib_normal** takes 0.00020684471130371094 time.      
The function **fib_recursion** takes 4.22707200050354 time.
The function **fib_tail_recursion** takes 0.0005285739898681641 time.

参考阅读

• 递归函数