如何将累加起始为s的t个连续数的Addup算法改写为递归算法？

好的，咱们先把原算法的核心逻辑捋清楚：Addup(s,t)的作用是计算从起始值s开始的t个连续整数的和——比如Addup(3,3)就是3+4+5，Addup(4,5)是4到8的5个数相加。要改成递归，关键是抓住递归的两个核心：终止条件和问题分解逻辑。

第一步：确定递归的终止条件 #

递归需要一个“停下来”的节点，也就是当问题小到不能再拆的时候直接返回结果。这里很明显：当t=1时，我们只需要返回s就够了——因为只有1个数要加，就是它本身。

第二步：拆解问题，写出递归表达式 #

我们有两种常见的拆解方式，都能实现需求：

方式一：从当前数出发，加上剩余数的和 #

我们可以把t个数的和拆成「第一个数s」加上「从s+1开始的t-1个数的和」。对应的递归表达式就是：
Addup(s, t) = s + Addup(s + 1, t - 1)

举个例子验证Addup(3,3)：

• Addup(3,3) = 3 + Addup(4,2)
• Addup(4,2) = 4 + Addup(5,1)
• Addup(5,1) = 5（触发终止条件）
• 最终计算：3+4+5=12，和原算法结果一致。

对应的伪代码：

function Addup(s, t):
    if t == 1:
        return s
    else:
        return s + Addup(s + 1, t - 1)

方式二：先算前t-1个数的和，加上最后一个数 #

另一种思路是：先计算前t-1个数的和，再加上第t个数（也就是s + t - 1，因为从s开始数第t个数是s + t -1）。对应的递归表达式是：
Addup(s, t) = Addup(s, t - 1) + (s + t - 1)

同样用Addup(3,3)验证：

• Addup(3,3) = Addup(3,2) + 5
• Addup(3,2) = Addup(3,1) + 4
• Addup(3,1) = 3（触发终止条件）
• 最终计算：3+4+5=12，同样正确。

对应的伪代码：

function Addup(s, t):
    if t == 1:
        return s
    else:
        return Addup(s, t - 1) + (s + t - 1)

总结 #

这两种递归实现都完全符合原算法的功能，核心都是把大问题拆解成更小的子问题，直到触发t=1的终止条件。你可以根据自己的习惯选择其中一种。

内容的提问来源于stack exchange，提问作者Pickslides