学习记录-递归函数的设计

递归函数设计有三要素：

• 明确函数的目标
• 找递归终止条件
• 找等价关系式

例：给定一个无序数组，希望找出其中的最长递增子序列的长度，设计递归函数完成。

本文暂不考虑时间复杂度。

1. 明确函数的目标

顾名思义，要知道函数需要做什么事情。

在上面的例子中，函数的目标就是找到最长递增子序列的长度，于是我们考虑设计函数L(nums, i) ，它接受数组nums 和起始索引i ，找到从这个索引开始的最长递增子序列的长度：

def L(nums, i):
    # do something here...
    max_len = 1    # save max length
    # do something here...
    return max_len

L 函数的基本思路应当为：从i 号索引开始，每次从i 后面的一个子序列中开始找能够比nums[i] 大的数字，并且记录下长度，保存最大长度。

例如nums=[1, 5, 2, 4, 3] ，若i = 0 ，则从[5, 2, 4, 3] 中找，结果将会是3。

2. 递归终止条件

一般终止条件是通过长度或比较某些关系来确定的，比如某个数大了/小了，就要结束递归，或者我递归到了数组的末尾也没有找到希望的结果，此时无论如何都要返回来结束递归，在本例中，递归的终止条件就是数组遍历到了末尾，因此：

def L(nums, i):
    if i + 1 == len(nums):
        return 1
    max_len = 1
    # do something here...
    return max_len

如果到了数组的末尾，那么这个最长递增子序列就只有这末尾一个数字，所以返回1 。

但是，不仅如此，如果我们找到了最长子序列，也是需要返回的。

3. 等价关系式

这个通常是比较困难的，个人认为能否找到等价关系式才是这个函数究竟能否设计为一个递归函数的关键因素，这也将成为递归函数的主体部分。

在本例中，不难发现的是，第i 个元素后面有多少个比它大的数，是由第i + 1 开始的子序列决定的，所以第i 个元素的最长递增子序列长度应当为1 + L(nums, i + 1) ，所以函数就能够写为：

def L(nums, i):
    if i + 1 == len(nums):
        return 1
    max_len = 1
    for j in range(i + 1, len(nums)):
        if nums[i] < nums[j]:
            max_len = max(1 + L(nums, j), max_len)
    return max_len

另外，需要注意的一点是，递归函数返回什么，何时返回。何时返回由终止条件决定，返回什么东西是由函数目标决定的，这里我们需要找最长递增子序列的长度，所以返回的内容就是这个长度的值。

代码详见：https://cloud.zzbloc.top/s/NBtM