CODEWITHSUNDEEP
pythonpython-3.xrecursionfibonacciyield
N.Elsayed
N.Elsayed

Reputation: 484

Recursive Fibonacci with yield

i am trying to build a Fibonacci function with yield here in this code, my problem is

How to use yield in recursion and recursive calls 

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);

I get this error

"unsupported operand type(s) for +: 'generator' and 'generator'"

I am in need to know how to use yield with recursion without get this error

Upvotes: 2

Views: 1781

Answers (1)

Paritosh Singh
Paritosh Singh

Reputation: 6246

You want the power to shoot yourself in the foot.

Well, here you go. Introducing "yield from" in python 3.3+ in PEP 380

"forward recursive yield" (This will behave similar to how you would expect generators to behave.)

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

Note that this will error out once the maximum recursion depth is reached.

This however does not really satisfy how we tend to think of a usual recursive function that tries to work downwards. However, it seems that we could simplify our recursive function to a tail recursive function, we could introduce yield and utilize it.

Attempt 2: "backward recursive yield"

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]

note however that we get our output in one "next" call. What happens now with a yield let loose?

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

We can make the function very slightly safer by introducing a return, for a final version.

Attempt 3: #safe for non-base cases.

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

I cannot think of a single scenario where you would want to create a recursive solution with yields, and the downsides of the setup seem immense. However, somethings are just meant to be explored for fun. This question made me curious enough to do some research on it. I will advise however, to never actually do this.

Upvotes: 2

Related Questions