Python进阶：递归算法

2019-01-27 本文已影响17人惑也

一、递归定义

如果函数中包含了对其自身的调用，该函数就是递归的；
递归(Recursion)，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法；
基本要素

基线条件：确定递归到何时终止，函数不再调用自己，也称为递归出口；
递归条件：函数调用自己，将大问题分解为类似的小问题，也称为递归体。

核心思想
每一次递归，整体问题都要比原来减小，并且递归到一定层次时，要能直接给出结果。

二、递归思想

递归算法常用来解决结构相似的问题。

所谓结构相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小，并且依赖第一部分的结果。

本质上，递归是把一个不能或不好解决的大问题转化成一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。

实际上，递归会将前面所有调用的函数暂时挂起，直到递归终止条件给出明确的结果后，才会将所有挂起的内容进行反向计算。其实，递归也可以看作是一种反向计算的过程，前面调用递归的过程只是将表达式罗列出来，待终止条件出现后，才依次从后向前倒序计算前面挂起的内容，最后将所有的结果一起返回。

三、构建函数

基线条件(base case)：递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果；
所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间；
基本结构

至少一个基线条件：通常在递归函数的开始位置，就设置基线条件；
一系列的规则：使得每次调用递归函数，都趋近于直至达到基线条件。

四、基本步骤

初始化算法：递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但可以为递归计算设置种子值；
检查要处理的当前值是否已经与基线条件相匹配(base case)。如果匹配，则进行处理并返回值；
使用更小的或更简单的子问题(或多个子问题)来重新定义答案；
对子问题运行算法；
将结果合并入答案的表达式；
返回结果。

五、递归应用

递归算法一般用于解决三类问题

数据的定义是按递归定义的，比如：Fibonacci函数、阶乘等；
问题的解法是按递归算法实现的，比如：回溯法；
数据的结构形式是按递归定义的，比如：树的遍历、图的搜索等；

优点

递归使代码看起来更加整洁、优雅；
递归可以将复杂任务分解成更简单的子问题；
使用递归比使用一些嵌套迭代更容易解决问题。

缺点

递归的逻辑很难调试、跟进；
递归的运行效率较低。因为在递归的调用过程中，系统会为每一层的返回值或局部变量开辟新的栈进行存储。递归次数过多容易造成栈溢出。

六、经典case：阶乘

阶乘：fact(n) = n! = 1 * 2 * 3 * 4 * ......* (n-1) * n = n * fact(n-1)
fact(n)，可以表示为 n * fact(n - 1)，只有n=1时需要进行特殊处理；
递归

非递归实现阶乘

def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
    return res 

print(factorial(4))
24

递归实现阶乘

def factorial(n):
    if n == 0 or n == 1: 
        return 1
    else: 
        return (n * factorial(n - 1))

print(factorial(5))
120

递归过程

factorial(5)                        # 第 1 次调用使用 5
5 * factorial(4)                    # 第 2 次调用使用 4
5 * (4 * factorial(3))              # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1 
5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
5 * (4 * (3 * 2))                   # 从第 4 次调用返回
5 * (4 * 6)                         # 从第 3次调用返回
5 * 24                              # 从第 2 次调用返回
120

Python默认的递归次数限制为1000，以避免耗尽计算机中的内存。

七、尾递归优化

在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多时，可能会导致栈溢出；
尾递归：指函数返回时调用自身本身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况；
尾递归和循环的效果是一样的，实际上，可以把循环看成是一种特殊的尾递归函数；
尾递归是优化递归防止溢出的一种方法，但并不能彻底解决溢出。举个形象的例子：开车减速慢行可以少出车祸，但减速慢行不一定不出车祸；
阶乘的fact(n)函数，return语句，返回了n * fact(n - 1)的乘法表达式，不是尾递归。要改成尾递归方式，需要把每一步的乘积传入到递归函数中。

参考代码如下：

def factorial(n):
    return fact_iter(n, 1)

def fact_iter(n, product):
    if n == 1:
        return product
    return fact_iter(n - 1, n * product)

print(factorial(5))
120

将每次的乘积，存入到 product 中，return fact_iter(n-1, n * product) 返回的仅仅是函数本身，n - 1 和 n * product 在函数调用前就会被计算出来，不影响函数调用；
优化的实质，就是将原本倒序的计算，通过 n * product 变为了正序的计算，还是递归的思想，但是不会占用其他的栈帧，因为所有的结果都已近存放在了 product 中。fact(5)对应的fact_iter(5, 1)的调用如下：
```
===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120
```
尾递归调用时，如果做了优化，栈不会增长，无论多少次调用也不会导致栈溢出。
遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，任何递归函数都存在栈溢出的问题。所以，即使把上面的fact(n)函数改成尾递归方式，也可能导致栈溢出。

八、常用算法

斐波拉契数列

数列：规定F(0) = 0，F(1) = 1，从第三项起，每一项都等于前两项的和，即F(N) = F(N - 1) + F(N - 2) (N >= 2)
参考代码

def fibonacci(n):
    if n < 2:
        return n 
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))
55

n项指定值之和

s = a * 1 + a * 2 + a * 3 + a * 4 + ...... + a * n，SSS(a, n) = SSS(a, n-1) + a * n
参考代码

def n_sum(a, n):
    if n == 1:
        return a
    return n_sum(a, n - 1) + n * a 

print(n_sum(2, 5))
30

快速排序

原理：基于分治策略，设定一个基准线(pivot)，将数据与基准线对比，分成大于和小于两部分，通过递归，不断分治实现数据的排序；
参考代码

def quick_sort(n):
    if len(n) < 2:
        return n 
    else:
        pivot = n[0]
        left = [x for x in n[1:] if x < pivot]
        right = [x for x in n[1:] if x > pivot]
    return quick_sort(left) + [x for x in n if x == n[0]] + quick_sort(right)

print(quick_sort([5,11,3,5,8,2,6,7,3]))
[2, 3, 3, 5, 5, 6, 7, 8, 11]