stack-based emulation of recursive fibonacci function - turns out it is slower in pypy and cpython

gistfile1.py

def fib_rec(n):
    if n <= 2:
        return 1
    else:
        return fib_rec(n - 1) + fib_rec(n - 2)


def fib_stack(n):
    value_stack, op_stack = [], [n]
    while True:
        if not op_stack:
            return value_stack[-1]
        n = op_stack.pop()
        if n is None:
            value_stack.append(value_stack.pop() + value_stack.pop())
        elif n <= 2:
            value_stack.append(1)
        else:
            op_stack.extend([None, n - 1, n - 2])