——尾递归的应用
这是《编程之美》中2.14节提出的一个问题，问题的描述为
一个有N个整数元素的一维数组(A[0], A[1], …, A[n-2], A[n-1])，这个数组有很多子数组，那么子数组之和的最大值是什么？
以往遇到这种问题的第一种思维模式也像书中的第一种解法一样去枚举出所有的子数组，对每个子数组内部元素求和，然后找出所有和中最大的。这是一种分解问题的思路，但所分解的子问题已经偏离了原始的问题。比如第一步的分解就是枚举所有的子数组，单就这步就已经是\(O(n^2)\)了，而后的两个子问题，一个是内部元素求和，另一个是找出所有和中最大的，这两个问题与原问题也不具有太多的共性，因而能够由此想到最优的算法极为困难。
书中的解法二用了递归分解子问题的思路，却没有给出适当的语言描述，使用了循环。用循环去描述，对思考者而言不是一种好的语言，正如我在《尾递归的启示》一篇中写的那样，循环是一种机器友好的语言。这篇文章，我将会用纯粹地过程调用的方式来完成这个问题的解答，最终得到的优化算法与《编程之美》中提到的最后一种解法是等价的。当然递归子问题的分解与解法二也不太一样。
对于原问题，可以分解为以下两个子问题：
- 求不包含A[0]的所有子数组之和的最大值；
- 求包含A[0]的所有子数组之和的最大值。
原问题的解就是两个子问题解的较大者。显然，第一个子问题是原问题的递归，不包含A[0]的所有子数组，意味着(A[1], A[2], …, A[n-1])的所有子数组。第二个问题是一个新的子问题，但比原问题要简单的子问题。假设我们记原问题为sub_arr_max，数组A为arr，数组的起始坐标为s，结束坐标为e，第二个子问题为max_of_all_subs，那么以上的分解，很容易翻译为以下的代码
def sub_arr_max(arr, s, e):
if s == e:
return arr[s]
else:
return max(sub_arr_max(arr, s+1, e), max_of_all_subs(arr, s, e))接下来是如何解决子问题max_of_all_subs。先回顾这个子问题的含义，这个子问题是说所有包含arr[s]元素的子数组元素和中，最大的值。这个子问题可以进一步分解为两个子问题：
- 求不包含arr[e]的数组中所有包含arr[s]的最大值；
- 求数组arr[s..e]所有元素的和。
这个问题的分解中，第一个子问题又一次是原问题的递归，而第二个子问题是一个更为简单的递归问题。假设记第二个子问题为sum_of_all，那么以上的问题分解可以立刻翻译为
def max_of_all_subs(arr, s, e):
if s == e:
return arr[s]
else:
return max(max_of_all_subs(arr, s, e-1), sum_of_all(arr, s, e))解决子问题sum_of_all是一个常见的线性递归，可以表述为，当s > e时，
\(sum\_of\_all (arr, s, e) = \)
\(sum\_of\_all(arr, e, e-1) + arr[e]\)
直接翻译以上的递归式就能得到下面的解法
def sum_of_all(arr, s, e):
if s == e:
return arr[s]
else:
return sum_of_all(arr, s, e-1) + arr[e]以上就是一个完整可以运行的解法，并且很容易调试错误，作为寻找优化算法的起点。为了不偏离本文的核心要义，且不去分析这样的解法中有多少的重复计算和空间浪费。直接将三个过程依次改造为尾递归的形式，这个改造过程中，不仅会找到最优的解法，并且能够洞察原问题中的一些特殊性，算法分析也附带会变得清楚。
第一步：改造sum_of_all
sum_of_all方法是一个线性递归的过程，我们可以在参数中增加一个变量res来记录从第一个元素arr[s]开始累加到s[e]的结果，每次递归调用只需要增加s即可。这个改造过程与《尾递归的启示》中提到的阶乘的改造过程几乎是相同的。一种写法如下：
def tsum_of_all(arr, s, e, res):
if s > e:
return res
else:
return tsum_of_all(arr, s+1, e, res+arr[s])为了区分与前面算法的不同，重命名为tsum_of_all，t代表tail recursion的意思。有了新方法，在max_of_all_subs中可以这样调用
def max_of_all_subs(arr, s, e):
if s == e:
return arr[s]
else:
return max(max_of_all_subs(arr, s, e-1), tsum_of_all(arr, s, e, 0))或者
def max_of_all_subs(arr, s, e):
if s == e:
return arr[s]
else:
return max(max_of_all_subs(arr, s, e-1), tsum_of_all(arr, s＋1, e, arr[s]))两种写法等价。这里之所以要写出这两种，其实是想提醒，新增变量的初始值一定要注意，0是个很特殊的值，有些情形下并不能初始为0，第二步的改造中就会遇到这样的问题。
第二步：改造max_of_all_subs
max_of_all_subs求解了arr[s], arr[s..s+1], arr[s..s+2], .., arr[s..e]中，所有数组各自求和中最大的那个。用动态规划的思路，就是从小的开始求解，arr[s]显然就是自己，而后的每一个，比如arr[s..s+i]，等于arr[s..s+i-1]的最大解和arr[s..s+i-1]的和加arr[s+i]两者比较的较大者。在求arr[s..s+i-1]时，可以保存两个结果，一个是arr[s..s+i-1]的最大解，记为res，另一个是arr[s..s+i-1]的和，记为ss，即sum_of_all问题已经融入到了问题的迭代中。改造后的算法如下
def tmax_of_all_subs(arr, s, e, res, ss):
if s > e:
return res
else:
return tmax_of_all_subs(arr, s+1, e, max(res, ss+arr[s]), ss+arr[s])为了区分与前面算法的不同，重命名为tmax_of_all_subs。当在sub_arr_max中使用这个方法时候，需要注意的是，初始值res不能为0，理由是如果数组中的元素都是负数，那么所有的子数组和都无法比0大，造成错误。因而调用时候要从第一个元素开始
def sub_arr_max(arr, s, e):
if s == e:
return arr[s]
else:
return max(sub_arr_max(arr, s+1, e), tmax_of_all_subs(arr, s+1, e, arr[s], arr[s]))第三步：改造sub_arr_max
回顾改造尾递归的两个要素之一是从小问题开始，寻找合适的变量来记录中间结果。如果数组是一个元素，直接返回结果，如果是两个元素，我们可以记录一个元素时候的结果，然后同新加入元素之后的结构进行比较。最开始自顶向下考虑问题时，我们从A[0]元素开始划分，A[1..N-1]同原问题有着同样的结构，而从自底向上考虑时，可以反过来想，考虑到第i个元素时A[0..i-1]同原问题有着同样结构的子问题，而A[0..i]需要解决的是max_of_all_subs的问题。这时我们能够改写出一个tmax_of_all_subs的一个对称写法。
def tmax_of_all_subs(arr, s, e, res, ss):
if s > e:
return res
else:
return tmax_of_all_subs(arr, s, e-1, max(res, ss+arr[e]), ss+arr[e])在sub_arr_max中最终比较的两个对象，其一是与原问题有着同样结构子问题的值，我们可以用一个变量去记录这个值，其二是tmax_of_all_subs问题，我们不需要每次去重算，只需要保存arr[s..e-1]中的最大值，能比较的是保存的最大值+arr[e]和arr[e]的比较中较大的作为新的保存值。为什么保存的arr[s..e-1]中最大值可以加arr[e]？因为这个最大值一定包含arr[e-1]，维护了tmax_of_all_subs这个问题求值的结构。如同在第二步中省去sum_of_all一样，这个问题中我们一样可以省去max_of_all_subs。由此就得到了最终的解法
def tsub_arr_max(arr, s, e):
return tsam(arr, s+1, e, arr[s], arr[s])
# res保存的是数组arr[0..s]的最优解
# toas保存的是arr[0..s]中一定包含arr[s]的最优解
def tsam(arr, s, e, res, toas):
if s > e:
return res
else:
toas = max(arr[s], toas+arr[s])
return tsam(arr, s+1, e, max(res, toas), toas)对照《编程之美》上的循环解法，容易看出，这两种写法运用了相同的思路，然而整个的思考过程却是不同的，对我而言，改写尾递归的方式更容易些。
相关阅读
- 尾递归的启示?⭐️⭐️⭐️⭐️⭐️
