递归

文章目录

引言

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

概念

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

日常事例

  • 查字典
  • 阅读维基百科(内链)

图示

自然界中的递归

生活中中的递归

特点

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

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

参考阅读