Функция рекурсии в двух типах для последовательности Фибоначчи - PullRequest
Новая
       41

Функция рекурсии в двух типах для последовательности Фибоначчи

0 голосов
/ 27 марта 2020

Это оригинальный код последовательности Фибоначчи с использованием рекурсии 

def rec(n):
if n<=1:
    return n
else:
    return ( rec(n-1) + rec(n-2))

n=int(input())

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

Следующий код, который я возвратил, также в основном является рекурсией. 

n=int(input())
n1,n2,count=0,1,0
def rec(n,n1,n2,count):
    if count<n:
        print(n1)
        nth=n1 + n2
        n1=n2
        n2=nth
        count+=1
        rec(n,n1,n2,count)
rec(n,n1,n2,count)

Мой вопрос: оба эти подхода следуют рекурсии (как настоящая рекурсия)?

Ответы [ 3 ]

1 голос
/ 27 марта 2020

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

Хвостовая рекурсивная функция может легко конвертируется в циклы: 

def rec(n, n1=0, n2=1, count=0):
    while count < n:
        print(n1)
        n1, n2, count = n2, n1 + n2, count +1
0 голосов
/ 27 марта 2020

Ну, они оба рекурсия, потому что вы вызываете функцию a() внутри себя. Итак, основное различие в обеих ваших функциях состоит в том, что есть два рекурсивных вызова для первого и только один для второго.

Итак, теперь по другому вопросу:

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

Что ж, вы можете сделать что-то интересное, чтобы сделать это быстрее. Видите, из-за рекурсивного определения последовательности Фибоначчи, вы выполняете одни и те же вычисления более чем один.

Например: представьте, что вы должны вычислить fibonacci(5), поэтому вам нужно вычислить fibonacci(4) и fibonacci(3). Но теперь для fibonacci(4) вам нужно вычислить fibonacci(3) и fibonacci(2) и так далее. Но подождите, когда вы закончите sh вычисления fibonacci(4) ветви, вы уже вычислили все Фибоначчи для 3 и 2, поэтому, когда вы go вернетесь к другой ветви (fibonacci(3)) из первого рекурсивного вызова, вы уже вычислили Это. Итак, что, если есть способ сохранить эти вычисления, чтобы я мог получить к ним доступ быстрее? Вы можете сделать это с помощью Decorators , чтобы создать класс memoize (своего рода память, чтобы избежать повторных вычислений):

Таким образом, мы будем хранить каждое вычисление fibonacci(k) для dict, и мы будем каждый раз перед вызовом проверять, существует ли он в словаре, возвращать, если True, или вычислять его. Этот способ быстрее 

class memoize:
    def __init__(self, function):
        self.f = function
        self.memory = {}

    def __call__(self, *args):
        if args in self.memory:
            return self.memory[args]
        else:
            value = self.f(*args)
            self.memory[args] = value
            return value

@memoize
def fib(n):
  if n <= 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

r = fib(50)
print(r)

Вы можете видеть, что без памятка это заняло слишком много времени, а с памятка это заняло 0.263614.

Надеюсь, это поможет

0 голосов
/ 27 марта 2020

Если функция вызывает себя, она считается рекурсивной.

Разница между вашими двумя реализациями заключается в том, что первая вызывает себя примерно 2 ** n раз, вторая вызывает себя примерно n раз.

Для n = 50, 2 ** 50 - это 1125899906842624. Это много звонков! Неудивительно, что это занимает много времени. (Пример: подумайте, сколько раз вызывается rec(10) при вычислении rec(50). Много, много, много раз.)

Хотя обе ваши функции рекурсивны, я бы сказал, что последняя «прямая итерация», в которой вы по сути продвигаетесь вперед по последовательности Фибоначчи; для вашего второго rec(50) эта функция рекурсивно повторяется примерно 50 раз.

Одна из техник для ускорения рекурсивных вызовов называется memoization . См. «Заметки» в Википедии . Он работает путем немедленного возврата, если ответ был предварительно рассчитан ... тем самым не "повторяется".

...