递归

递归是一种解决问题的方法，精髓在于：

将问题分解为规模更小的相同问题；
持续分解，直到问题规模小到可以用非常直接的方式解决；
递归的问题分解方式非常独特，算法上的明显特征就是在算法流程中调用自身。

引言：数列求和

给定一个列表，返回所有数的和。

要求不用循环或数列求和公式，考虑递归做法。

分析：

迭代格式：数列之和 = 首位数 + 余下数列之和；

分解求和过程，并且分解后的问题也是相同问题（更小的数列求和问题），即要求调用自身。
终止条件：数列之和 = 首位数。

数列规模少到只有1个的情况，即最小规模。

Python实现如下：

def listSum(array):
    if len(array) == 1:
        return array[0] # 规模最小的情况
    else:
        return array[0] + sumList(array[1:]) # 分解问题

对这个递归过程进行分析，可以发现这里面形成了一个递归调用栈。

不断开辟内存空间对问题进行分解，然后逐层返回结果。（后开辟的内存空间先返回 $\rightarrow$ 栈的LIFO特性）

递归的三定律

递归算法必须有一个基本结束条件（最小规模问题的直接解决）；
递归算法必须能改变状态向基本结束条件演进（减小问题规模）；
递归算法必须调用自身（解决减小了规模的相同问题）。

调用自身是递归算法中最难理解的部分，不用深究递归栈，只要理解为“问题分解成了规模更小的相同问题”即可。

递归调用的实现

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈。

每次调用，压入栈的现场数据称为栈帧；
当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场。

递归过程就是不断将现场数据压入栈中，然后不断弹出栈帧返回结果。

在调试递归算法程序时，会经常碰到RecursionError（Python）错误，即递归的层数超出了系统调用栈的容量限制。

导致这种无限递归的原因：

无基本结束条件；
向基本结束条件演进太慢。

在Python内置的sys模块可以获取和调整最大递归深度：

import sys
sys.getrecursionlimit()
>>> 3000
sys.setrecursionlimit(4000)
sys.getrecursionlimit()
>>> 4000

递归的应用（例题）

任意进制转换

分析：

$n$ 进制有 $n$ 个不同的符号（ $n<17$ ）：0123456789ABCDEF；
终止条件：比目标进制 $n$ 小的整数，转换成 $n$ 进制直接查表即可；
迭代格式：待求数的余数列表 = 待求数整除 $n$ 后的余数列表（调用自身） + 待求数除以 $n$ 的余数

Python实现如下：

def divide_by_n(dec_num, n):
    digits = "0123456789ABCDEF"
    if dec_num < n:
        return digits[dec_num] # 规模最小的情况
    else:
        return divide_by_n(dec_num // n, n) + digits[dec_num % n] # 分解问题

汉诺塔

分治策略

分而治之：

解决问题的典型策略；
将问题分为若干个更小规模的部分；
通过解决每一个小规模部分问题，并将结果汇总得到原问题的解。

递归方法体现了分治策略，并且这种方法应用相当广泛，如应用于排序、查找、遍历、求值等。

优化问题之动态规划

计算机科学中许多算法都是为了找到某些问题的最优解。

如，两个点之间的最短路径；最好匹配一系列点的直线；满足一定条件的最小集合。

引言：找零兑换问题

问题描述：用什么策略使得自动售货机每次给顾客最少数量硬币？

策略：使用尽可能多的大面值的硬币。

贪心策略

贪心策略（Greedy Method）：每次都试图解决问题的尽量大的一部分。

对应到兑换硬币问题，即：每次以最多数量的最大面值硬币来迅速减少找零面值。

但贪心策略也会有失效的情况，以找零问题为例：

需要找零63；
硬币有25、21、10、3、1的面值；
若用原来的策略，则 $63 = 25\times 2 + 10\times 1 + 1\times 3$ ，共计6个硬币；
而实际上，最优策略为 $63=21*3$ ，共计使用3个硬币。

递归解法

基本结束条件：剩下兑换的零钱 = 某种硬币的面值；
迭代格式（减小硬币规模）：对每种硬币尝试一次（递归调用）；然后选择各种情况中使用最少数量的方案：

$\text{numCoins} = min \left\{\begin{array}{c} 1 + \text{numCoins}(\text{originalAmount} - \text{Coin1}) \\ 1 + \text{numCoins}(\text{originalAmount} - \text{Coin2}) \\ 1 + \text{numCoins}(\text{originalAmount} - \text{Coin3}) \\ \cdots \\ \end{array}\right.$

以25、21、10、3、1的面值硬币为例：

def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1 # 最小规模
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i) # 减小问题规模
            if numCoins < minCoins:
                minCoins = numCoins # 记录使用的硬币数量
    return minCoins

相当于尝试所有的排列可能性，然后选出最小的那种排列 => 效率十分低下，重复计算过多。

改进：消除重复计算。利用一个表，将中间计算结果保存起来，在计算之前查表看看是否已经计算过。

而这个中间结果即部分找零的最优解（在递归调用中，已经得到的最优解被记录下来）：

def recMC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1 # 记录表格
        return 1 # 最小规模
    elif knownResults[change] > 0: # 表格一旦有记录，则说明已得对应零钱需要兑换硬币数量的最优解
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins # 记录表格
    return minCoins

此时，通过额外的存储空间的使用（knownResults），换来了极高的效率。

这种做法可以称为memoization（记忆化/函数值缓存/备忘录技术），但不能称为动态规划。

动态规划解法

动态规划：一种更有条理的解决优化问题的方式。

最优化问题可以用动态规划策略解决的前提条件：问题的最优解包含了更小规模子问题的最优解。

大问题的最优解可以通过小问题最优解的累加来获得。

以找零兑换问题为例，其动态规划算法从最简单的0分钱找零的最优解开始，逐步递加上去，直到我们需要的找零钱数。

在递加过程中，设法保持每一分钱的递加都是最优解，一直加到找零钱数，最终得到的解即为最优解。

做法如下：

def dpMakeChange(coinValueList, change, minCoins):
    # 从1分钱开始到change，逐个计算最少硬币数
    for cents in range(1, change+1):
        # 1. 初始化一个最大值（相当于全用1分钱的硬币），以后才会越来越小
        coinCount = cents
        # 2. 减去每个硬币，向后查**表**找最少硬币数，同时记录找对应零钱的硬币的最少数
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
        # 3. 得到当前最少硬币数，记录到表中
        minCoins[cents] = coinCount
    # 返回要求找零数对应的硬币数
    return minCoins[change]

这里的minCoins相当于建立了一张表，而这张表是从最小问题的最优解逐渐建立起来的；
该表minCoins的最小问题其实是：0元钱找零0个硬币。

虽然该问题是以递归的方式进行分析，但最后得到的是一个更有条理的高效非递归算法。

可以看出，动态规划的主要思想：

从最简单的情况开始，到达所需找零的循环；
每一步都依赖以前的最优解，直到得到答案。

上述算法已经得到了最少硬币数量，但未返回硬币是如何组合的，解决思路很简单：

更新找零硬币数时，跟踪记录所减去的硬币值（相当于该零钱必定需要这个硬币）；那么每个零钱都对应一个必要硬币值，形成和minCoins一样大小的表coinUsed；
得到最优解后，减去选择的硬币币值，回溯到表格coinUsed中进行查找，就能逐步得到每一步所选择的硬币币值。

def dpMakeChange(coinValueList, change, minCoins, coinUsed):
    # 从1分钱开始到change，逐个计算最少硬币数
    for cents in range(1, change+1):
        # 1. 初始化一个最大值（相当于全用1分钱的硬币）
        coinCount = cents
        newCoin = 1 # 初始化新加硬币的面值
        # 2. 减去每个硬币，向后查找最少硬币数，同时记录总的最少数
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newCoin = j # 记录当前硬币面值
        # 3. 得到当前最少硬币数，记录到表中
        minCoins[cents] = coinCount
        coinUsed[cents] = newCoin # 记录本步骤加入了哪个硬币面值
    # 返回最后一个结果
    return minCoins[change]

def printCoins(coinsUsed, change):
    coinList = []
    coin = change
    while coin:
        thisCoin = coinsUsed[coin]
        coinList.append(thisCoin)
        coin = coin - thisCoin
    print(coinList)

动态规划的案例分析（例题）

博物馆大盗问题

问题：大盗潜入博物馆，面前5件宝物，分别由重量和价值，大盗的背包仅能负重20公斤，如何选择宝物才能使总价值最高？

Item	Weight	Value
1	2	3
2	3	4
3	4	8
4	5	8
5	9	10

分析：

设问题求解函数为 $m(i,W)$ ，表示：前 $i$ 个宝物中，组合不超过 $W$ 重量的最大价值。

该函数其实就是本题的动态规划表格。
那么，问题分解如下：
m(i,W) = \left\{\begin{array}{} 0, & \text{if } i = 0 \text{ or } W = 0 \\ m(i-1, W), & \text{if } w_i > W \text{ 装不下第i个宝物}\\ \max\{m(i-1, W),\ m(i-1, W-w_i)+v_i\}, & \text{otherwise} \text{ 不装第i个宝物与装第i个宝物的价值比较} \end{array}\right.
针对该问题，相当于从 $m(1,1)$ 算到 $m(5,20)$ 。

做法如下：

# 宝物的重量和价值
tr = [None, {'w':2, 'v':3}, {'w':3, 'v':4}, {'w':4, 'v':8}, {'w':5, 'v':8}, {'w':9, 'v':10}]

# 大盗最大承重
max_w = 20

# 初始化规划表格
m = {(i,w):0 for i in range(len(tr)) for w in range(max_w + 1)}

# 逐个填写该表格
for i in range(1, len(tr)):
    for w in range(1, max_w + 1):
        if tr[i]['w'] > w:
            m[(i, w)] = m[(i-1, w)]
        else:
            m[(i, w)] = max(
                        m[(i-1, w)],
                        m[(i-1, w-tr[i]['w'])] + tr[i]['v'])

print(m[(len(tr)-1), max_w])