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
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.
