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)