python - 将递归函数重写为迭代方法

Question

你将如何在没有递归的情况下重写这个 python 代码？

def f(n):
   if n == 1:
       return 2
   elif n == 2:
       return 1
   elif n == 3 or n == 4:
       return n
 
   r1 = f(n-1)
   r2 = f(n-2)
   r3 = f(n-3)
   r4 = f(n-4)
 
   return (r1+r2+r3)/r4

标签： pythonrecursion

Answer 1

您可以保留初始条件，然后使用r1, r2, r3, r4when的值n=5。然后迭代直到你达到你的n, 通过旋转值并计算下一个比率

def f_vars(n):
    initial_values = [2, 1, 3, 4]
    if n <= len(initial_values):
        return initial_values[n - 1]

    r3, r2, r1, next_n = initial_values

    for _ in range(n - 4):
        r4, r3, r2, r1 = r3, r2, r1, next_n
        next_n = (r1 + r2 + r3) / r4

    return next_n

使用数组也可以实现，但性能较低

def f_array(n):
    initial_values = [2, 1, 3, 4]
    if n <= len(initial_values):
        return initial_values[n - 1]

    for _ in range(n - 4):
        initial_values.append(sum(initial_values[1:]) / initial_values[0])
        initial_values.pop(0)

    return initial_values[-1]

---

一些时间信息

• n=10_000_000并且f_vars需要大约2sec
• n=10_000_000并且f_array需要大约10sec
• n=29并且f (recursive)需要大约12sec