Рекурсивная Фибоначчи с доходностью - PullRequest
Новая
       53

Рекурсивная Фибоначчи с доходностью

0 голосов
/ 11 ноября 2018

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

Как использовать yield в рекурсивных и рекурсивных вызовах 

def fib(x):
  if(x==0 or x==1 ):
   yield  1
  else:
    yield fib(x-1)+fib(x-2)

y=[i for i in fib(10)]
print(y);

Я получаю эту ошибку

"неподдерживаемые типы операндов для +: 'generator' and 'generator'"

Мне нужно знать, как использовать yield с рекурсией без получения этой ошибки.

1 Ответ

0 голосов
/ 11 ноября 2018

Вы хотите, чтобы сила стреляла себе в ногу.

Ну вот, пожалуйста. Введение «доходности» в python 3.3+ в PEP 380

"прямая рекурсивная доходность" (Это будет вести себя подобно тому, как вы ожидаете, что генераторы будут вести себя.) 

def fib_infinity(start = 0, acc = 1):
    yield start + acc
    yield from fib_infinity(acc, start + acc)

i = fib_infinity()
next(i) #1
next(i) #2
next(i) #3
next(i) #5
next(i) #8

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

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

Попытка 2: «обратный рекурсивный доход» 

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

y = [next(fib(i)) for i in range(10)]
#[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

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

i = fib(8)
next(i) #21
next(i) #21
next(i) #RecursionError: maximum recursion depth exceeded in comparison

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

Попытка 3: # безопасно для неосновных случаев. 

def fib(n, a = 0, b = 1): 
    if n == 0:
        yield a
        return 0
    if n == 1: 
        yield b
        return 0
    yield from fib(n - 1, b, a + b)
i = fib(8)
next(i) #21
next(i) #StopIteration

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

...