DEV Community

Discussion on: Fibonacci without recursiveness in Python - a better way

Collapse
 
paddy3118 profile image
Paddy3118 • Edited

Hi again, I was researching a similar sequence, the padovan sequence which is like the fibonacci, but P[n] = P[n-2] + P[n-3]. In that code I keep only the last four terms of a list turned into a deque with the following code:

def padovan_r() -> Generator[int, None, None]:
    last = deque([1, 1, 1], 4)
    while True:
        last.append(last[-2] + last[-3])
        yield last.popleft()
Enter fullscreen mode Exit fullscreen mode

Similar could be done to save memory in Fibonacci.

Collapse
 
joaomcteixeira profile image
João M.C. Teixeira

Hi,
That is also a very nice implementation if you don't want to keep a list of the whole sequence. Going forward in the discussion, we can actually avoid using deque and increase the speed almost by two.

def padovan_j():
    last = 1
    prev1 = 1
    prev2 = 1
    prev3 = 1
    while True:
        yield prev3
        last = prev2 + prev3
        prev1, prev2, prev3 = last, prev1, prev2
Enter fullscreen mode Exit fullscreen mode