递归算法

递归调用

简介

有一个很古老的故事是这样讲的

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

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

。。。

除非讲故事的人自己停下来不讲了，不然这个故事可以无限讲下去，原因就是故事嵌套的故事就是故事本身，实际上这个就是语言的递归一个例子。

但上面的例子是没有结束条件的，如果设计到代码中就会陷入无限循环执行的死循环状态，无法为程序的设计人员解决事务。

当涉及解决问题时，递归是一种非常有用的编程技巧，为它设计一个出口，它允许函数调用自身以解决更小规模的问题，直到达到基本情况为止。

递归的基本原则

递归函数通常遵循以下原则：

• 定义基本情况 确定一个或多个输入的特殊情况，当满足这些条件时，递归函数将直接返回结果而不再调用自身。
• 减小问题规模 通过调用自身来解决一个规模更小的问题，这样每次递归调用都在问题规模上取得了进展。 也就是需要一个已定义好的规则来使其它非基本的情况转化为基本情况。
• 终止条件 递归函数必须包含能够导致函数不再递归调用的条件，以避免无限递归。

递归的使用

数学中有一个比较经典的递归算式就是求阶乘

一个正整数的阶乘 factorial 是所有小于及等于该数的正整数的积，并且 0 的阶乘为 1。自然数 n 的阶乘写作 n!。

对阶乘的定义进行分析：

• 首先定义 f(n) 为阶乘函数。它的结果就是阶乘计算之后的值。
• 从定义中能得到基本情况为: f(0) = 1, f(1) = 1
• 其它情况: f(2) = 2*1 = 2*f(1)，f(3) = 3*2*1 = 3*f(2) 即 f(n) = f(n-1) * n

示例：

def f(n):
    """
    实现计算 n 的阶乘
    return：n 阶乘计算之后的值
    """
    if n == 0 or n == 1:
        # 对应基本情况
        return 1
    return f(n - 1) * n  # 对应递归情况

大多数情况下的递归操作都可以使用循环所替代。

在使用递归时，要注意避免陷入无限调用而产生的内存溢出。