Python计算交叉递推序列的迭代函数转递归方法咨询

实现思路 #

• 核心逻辑是让递归函数每次同时返回对应n项的(U_n, V_n)，不需要拆分两个独立的递归函数，完全匹配原递推的关联关系
• 递归终止条件：n=0时直接返回初始值(1, 2)，对应题目给出的U0=1, V0=2
• 递归推导逻辑：先递归计算得到n-1项的(U_{n-1}, V_{n-1})，再代入题目给出的递推公式计算当前n项的两个值即可

代码实现 #

def myfunction_recursive(n=5):
    # 递归终止条件：n=0返回初始值
    if n == 0:
        return (1, 2)
    # 获取n-1项的计算结果
    u_prev, v_prev = myfunction_recursive(n-1)
    # 代入递推式计算当前项
    u_current = 2 * u_prev + 3 * v_prev
    v_current = u_prev + v_prev
    return (u_current, v_current)

注意事项 #

该实现和你原有的迭代实现输出完全一致，比如n=5时两个函数都会返回(1541, 610)。如果需要计算的n值超过Python默认递归深度限制（默认约1000），会触发递归深度报错，这种场景更推荐使用原有迭代实现。

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