Блог

Как бы вы переписали этот код на 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
 

Вы можете сохранить начальное условие, а затем использовать значения для r1, r2, r3, r4 when 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