递归

文章目录

1. 1. 引言
2. 2. 概念
3. 3. 日常事例
4. 4. 图示
5. 5. 特点
6. 6. 伪代码比较迭代和递归
7. 7. 代码

尾递归

1. 1. 注意
2. 2. 参考阅读

引言

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

概念

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

日常事例

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

图示

特点

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

表现在 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.

参考阅读

• 递归函数