如何实现迭代与递归的相互转换？附迭代函数转递归需求

先看原迭代实现的differences函数，它的作用是生成列表中相邻元素的差值列表：

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

递归版本实现 #

递归的核心是拆解问题：

• 终止条件：当输入列表长度≤1时，没有相邻元素可计算，返回空列表
• 递归步骤：先计算当前列表前两个元素的差值，再将这个差值与values[1:]递归处理的结果合并

代码如下：

def differences(values):
    # 终止条件：列表长度不足2，返回空列表
    if len(values) <= 1:
        return []
    # 计算第一个差值，再拼接剩余部分的递归结果
    return [values[1] - values[0]] + differences(values[1:])

逻辑验证 #

比如输入[1,3,5,7]，递归过程是：

1. 计算3-1=2，然后递归处理[3,5,7]
2. 计算5-3=2，递归处理[5,7]
3. 计算7-5=2，递归处理[7]，返回空列表
4. 逐层拼接得到[2,2,2]，和原迭代函数结果完全一致

原palindrome函数已经是递归实现，这里保留原代码：

def palindrome(word):
    if len(word) <=1:
        return True
    if word[0] != word[-1]:
        return False
    return palindrome(word[1:-1])

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