почему возникает ошибка максимального предела рекурсии при выполнении кода (1) и нет ошибки при выполнении кода (2) - PullRequest
Новая
       9

почему возникает ошибка максимального предела рекурсии при выполнении кода (1) и нет ошибки при выполнении кода (2)

0 голосов
/ 30 октября 2018

Итак, вот 2 кода питона ряда Фибоначчи, использующих рекурсивную функцию. Я хотел узнать разницу между этим кодом и почему код (1) не работает, а код (2) работает без ошибок?

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

def f(n):
   return f(n-1) + f(n-2)

n=8
f(n)

тогда как это работает: 

def f(n):
   if n == 0:
      return 0
   if n == 1:
      return 1
   else:
      return f(n-1) + f(n-2)

f(4)

1 Ответ

0 голосов
/ 30 октября 2018

Ваш первый код не может быть остановлен. Он не имеет базовых вариантов для n == 0 или n == 1, поэтому он будет продолжаться бесконечно вниз с отрицательными числами.

Если вы добавите: 

  if n <= 1:
      return 0

ты золотой. (хотя это очень неэффективная реализация Фибоначчи).

Почему это неэффективно, хорошо, потому что каждое поддерево вычисляется много раз. f (8) вызывает f (7) и f (6), но f (7) также вызывает f (6), поэтому вы получаете экспоненциальное рекурсивное дерево. Ваше время работы будет O (2 ^ n). Это действительно плохо, обычно вы не сможете вычислить fib для n даже до 50.

Вы можете сделать лучше, если включите памятку: 

from functools import lru_cache

@lru_cache(maxsize=None)
def fib2(n):
    if n <= 1:
        return n
    else:
        return fib2(n-1) + fib2(n-2)

Это будет помнить, если вы звонили f (n) раньше и возвращали ответ, который вы делали в прошлый раз. Теперь проблема в том, что вам нужно помнить предыдущие вызываемые номера, поэтому, хотя ваше время работы сократилось до O (n), ваше требование к пространству теперь тоже составляет O (n).

Вы можете улучшить это снова, отказавшись от рекурсивных функций, и идите 

def fib3(n):
if n == 0:
    return 0
f1 = 0
f2 = 1

for i in range(n-1):
    f1,f2 = f2, f1+f2
return f2

Это лучше, так как вы помните только два числа в любое время.

...