Быстрая рекурсия Фибоначчи

Ответ 1

может быть так:

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 if(term == 1) return val;
 return fib(term - 1, val+prev, val);
}

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

Ответ 2

Такие проблемы представляют собой линейные рекуррентные типы, и они решаются быстрее с помощью быстрого экспоненциального матричного преобразования. Здесь blogpost, который кратко описывает этот подход.

Ответ 3

Вы можете сделать довольно быструю версию рекурсивного Фибоначчи, используя memoization (это означает: сохранение предыдущих результатов, чтобы избежать их повторного вычисления). например, здесь доказательство концепции в Python, где словарь используется для сохранения предыдущих результатов:

results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]

Он быстро возвращается для входных значений, которые обычно блокируют "нормальную" рекурсивную версию. Просто имейте в виду, что тип данных int не будет достаточным для проведения больших результатов и рекомендуется использовать произвольные целые числа точности.

Другой вариант - переписать эту итеративную версию...

def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

... как хвосто-рекурсивная функция, называемая loop в моем коде:

def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)

Ответ 4

Я нашел интересную статью о проблеме с Фибоначчи

здесь фрагмент кода

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

# added iterative version base on C# example
def iterFib(n):
    a = 0
    b = 1
    i=31
    while i>=0:
        d = a * (b * 2 - a)
        e = a * a + b * b
        a = d
        b = e
        if ((n >> i) & 1) != 0:
            c = a + b;
            a = b
            b = c
        i=i-1
    return a

Ответ 5

Предположим, что вы хотите, чтобы число n-го фибра строилось с массивом, содержащим предыдущие числа

int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];

Ответ 6

Пример в JavaScript, который использует рекурсию и лениво инициализированный кеш для повышения эффективности:

var cache = {};

function fibonacciOf (n) {
  if(n === 0) return 0;
  if(n === 1) return 1;
  var previous = cache[n-1] || fibonacciOf(n-1);
  cache[n-1] = previous;
  return previous + fibonacciOf(n-2);
};

Ответ 7

алгоритм duedl0r, переведенный в Swift:

func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
    guard n > 0 else { return 0 }
    if n == 1 { return previous.1 }
    return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}

приведен пример:

fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3

Ответ 8

Хорошим алгоритмом для быстрого вычисления фибоначчи является (в python):

def fib2(n):
    # return (fib(n), fib(n-1))
    if n ==  0: return (0,  1)
    if n == -1: return (1, -1)
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    u_k_s, u_km1_s = u_k**2, u_km1**2  # Can be improved by parallel calls
    u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
    u_2km1 = u_k_s + u_km1_s
    u_2k   = u_2kp1 - u_2km1
    return (u_2kp1, u_2k) if r else (u_2k, u_2km1)

def fib(n):
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)

Если вам нужно очень быстрое вычисление, ссылки на libgmp и использовать функции mpz_fib_ui() или mpz_fib2_ui().

Ответ 9

Чтобы остановить экспоненциальный рост, вам нужно запомнить вычисленное значение.

• Просто используйте массив для хранения значения.
• Проверьте массив, если вы уже вычислили его.
• Если он найдет его, используйте его или иначе вычислите и сохраните.

Вот рабочий пример для быстрой рекурсии с использованием памяти.

Вычисление числа фибоначчи