fibonacciEmulateRecursion.py

callStack = []
callStack.append({'instrPtr': 'start', 'nthNumber': 10})
returnValue = None

while len(callStack) > 0:
    nthNumber = callStack[-1]['nthNumber']
    instrPtr = callStack[-1]['instrPtr']

    if instrPtr == 'start':
        print('fibonacci(%s) called.' % (nthNumber))
        if nthNumber == 1 or nthNumber == 2:
            # BASE CASE
            print('Call to fibonacci(%s) returning 1.' % (nthNumber))

            # "Returns" the value in returnValue.
            returnValue = 1
            callStack.pop()
            continue
        else:
            # RECURSIVE CASE
            print('Calling fibonacci(%s) (nthNumber - 1).' % (nthNumber - 1))

            # "Calling" fibonacci(nthNumber - 1)
            callStack[-1]['instrPtr'] = 'after 1st recursive call'
            callStack.append({'instrPtr': 'start', 'nthNumber': nthNumber - 1})
            continue
    elif instrPtr == 'after 1st recursive call':
        # Continuation of the recursive case.
        callStack[-1]['result'] = returnValue
        print('Calling fibonacci(%s) (nthNumber - 2).' % (nthNumber - 2))

        # "Calling" fibonacci(nthNumber - 2)
        callStack[-1]['instrPtr'] = 'after 2nd recursive call'
        callStack.append({'instrPtr': 'start', 'nthNumber': nthNumber - 2})
        continue
    elif instrPtr == 'after 2nd recursive call':
        callStack[-1]['result'] = callStack[-1]['result'] + returnValue
        print('Call to fibonacci(%s) returning %s.' % (nthNumber, callStack[-1]['result']))

        # "Returns" the value in returnValue.
        returnValue = callStack[-1]['result']
        callStack.pop()
        continue

print(returnValue)