求助：如何将迭代实现的differences函数改写为递归形式？

问题说明 #

需要将迭代实现的differences函数改写为递归形式。该函数接收任意长度的整数列表，计算列表中相邻元素的差值并返回差值列表。自行编写的递归代码输出错误，需要解决方案或提示。

原迭代实现代码 #

def differences(values):
    result = []
    for i in range(len(values) - 1):
        result.append(values[i + 1] - values[i])
        print(result)
    return result


differences([4, 3, 6, 8])

运行该代码会依次输出[-1]、[-1, 3]、[-1, 3, 2]，最终返回[-1, 3, 2]。

错误的递归尝试代码 #

def differences(values):
    result = []
    if len(values) == 0:
        return
    result.extend(values[len(values) - 1] - len(values) + 1)
    print(result)
    return differences(values[:-1])


differences([4, 3, 6, 8])

错误分析 #

• 基线条件错误：当列表长度为1时，同样没有相邻元素可计算，应该返回空列表，而非仅处理长度为0的情况。
• 差值计算逻辑错误：values[len(values) - 1] - len(values) + 1完全偏离需求，正确的相邻差值应为最后一个元素减去倒数第二个元素（values[-1] - values[-2]）。
• extend方法使用错误：extend需接收可迭代对象，直接传入数值会抛出类型错误，应使用append添加单个元素。
• 递归返回值处理错误：当前递归的结果未与后续递归结果合并，导致最终返回的是递归到空列表后的空值，无法累积正确的差值列表。

正确的递归实现 #

写法一：从前往后递归 #

def differences(values):
    # 基线条件：列表长度小于2时，无相邻元素，返回空列表
    if len(values) < 2:
        return []
    # 计算第一个相邻对的差值，拼接递归处理剩余列表的结果
    return [values[1] - values[0]] + differences(values[1:])

# 测试
result = differences([4, 3, 6, 8])
print(result)  # 输出: [-1, 3, 2]

写法二：从后往前递归（匹配原迭代结果顺序） #

def differences(values):
    if len(values) < 2:
        return []
    # 先递归处理前n-1个元素，再添加最后一对的差值
    return differences(values[:-1]) + [values[-1] - values[-2]]

# 测试
result = differences([4, 3, 6, 8])
print(result)  # 输出: [-1, 3, 2]

带中间打印的版本（与原迭代行为一致） #

如果需要和原迭代一样逐步打印中间结果，可调整为：

def differences(values, result=None):
    if result is None:
        result = []
    if len(values) < 2:
        return result
    # 计算当前第一个相邻对的差值
    diff = values[1] - values[0]
    result.append(diff)
    print(result)
    # 递归处理剩余列表
    return differences(values[1:], result)

# 测试
differences([4, 3, 6, 8])

运行后会依次输出[-1]、[-1, 3]、[-1, 3, 2]，与原迭代行为完全匹配。

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