Как избежать повторяющихся чисел в рекурсии Python

Question

есть стандартный цикл Фибоначчи записанный следующим кодом с помощью рекурсии но в данном коде вычисление повторяются, как избежать повторных вычислений

def fibonacci(n):
    if n in (1, 2):
        return 1
    if n in (3,):
        print(3,)

    return fibonacci(n-1) + fibonacci(n-2)


print(fibonacci(10))

Answer 1

В данном случае можно сделать это через цикл: при x = 0,1,2 значение возвращается напрямую, а иначе результат получается в цикле.

def fib(x):
    if x == 0:
        return 0
    if x == 1 or x == 2:
        return 1
    a, b = 1, 1
    for i in range(x - 2):
        a, b = b, a + b
    return b

Answer 2

Трудно вообразить себе рекурсию без повторных вычислений: нужно по очередному числу Фибоначчи вычислять следующее, но не понятно как это сделать. Но если есть пара последовательных чисел Фибоначчи, следующую пару вычислить проще некуда:

(f_n, f_n+1) = (f_n, f_n-1 + f_n)

Ради ускорения мы поменяли интерфейс функции, она теперь возвращает пару чисел вместо одного. Спрячем подробности реализации за красивым традиционным фасадом:

def fib(n):

    def fib(n):
        if n == 0:
            return 1, 0
        a, b = fib(n - 1)
        return b, a + b

    return fib(n)[1]

Или вычисления можно делать на аргументах функции, чтобы получить хвостовую рекурсию:

def fib(n):

    def fib(n, a, b):
        if n == 0:
            return a + b
        return fib(n - 1, b, a + b)

    return fib(n, -1, 1)

Если вспомнить формулы f_2n-1 = f_n-1² + f_n² и f_2n = (2f_n-1 + f_n)f_n, то можно сделать очень быструю рекурсию:

def fib(n):

    def fib(n):
        if n == 0:
            return 1, 0
        if n % 2 == 0:
            a, b = fib(n // 2)
            return a ** 2 + b ** 2, (2 * a + b) * b
        a, b = fib(n - 1)
        return b, a + b

    return fib(n)[-1]

БЛОГ НА HUSL

Как избежать повторяющихся чисел в рекурсии Python

Ответы (2 шт):