If you really wanted to do recursion with a stack then you would be implementing function calling yourself.

That means being able to put a value representing resume-running-from-here on the stack.

I made an example of it. This is recursive, but it does not use python’s call stack, instead it implements its own.

calling a function involves adding the current location to the stack, along with the arguments to the function

similarly, the return value is put on the stack before a routine exits, so that the caller can find that value on the top of the stack after calling a routine

that’s why yield is there. it is used to suspend execution to obtain a value from which execution can be resumed at that same location. this value is placed on the stack so that it gets executed again when the called routine finishes

```
def sum_to_one(n):
# create a stack and operations for it
stack = []
push = stack.append
pop = stack.pop
peek = lambda: stack[-1]
size = stack.__len__
def swap2():
stack[-2:] = reversed(stack[-2:])
# the recursive routine
def sum_to_one():
# base case does nothing - the result is the same as the argument, so
# leave it on the stack and return
if peek() == 0:
swap2()
yield
# recursively call self by putting self and the argument on the stack
push(peek() - 1)
push(self)
swap2()
push(sum_to_one())
yield
# then add the result to the argument by popping both and putting the
# result back to onto the stack
push(pop() + pop())
swap2()
yield
push(n)
push(sum_to_one())
# execute the stack
while size() > 1:
print([item if type(item) is int else item.__name__ for item in stack])
self = pop() # global variable referring to the current routine
next(self) # run it until it yields
# final result found on the stack
return peek()
print(sum_to_one(1))
print(sum_to_one(7))
print(sum_to_one(8))
```

I’m printing out the stack each time a routine is about to be called.

Keep in mind that the top of the stack is the end, not the beginning, because the stack is a list, and a list does operations at the end.

There’s only one routine. It has two parts, because it suspends. The first part puts the current value on the stack and calls itself recursively. While this part is running, the stack will grow.

The second part looks the same on the stack, because it’s the same routine, but it’s the second part of it, this part adds two numbers, this causes the stack to shrink again, because it pops two numbers and puts one back, it gets smaller. Note that there will be two adjacent numbers in the stack while this is happening, those are what will be added.

Because all intermediate values are put on the stack, you can also see where 28 “comes from”, because after each addition the result is put back on the stack.

fibonacci is a bit more difficult, because there are two recursive calls in the recursive case.

```
def fib():
if peek() in [0, 1]:
# base case, result same as input, leave it on the stack
swap2()
yield
# obtain fib(n-1) and fib(n-2) through recursion
# put self to the stack as the return location
# put n-1 as the argument
# put fib as the next routine to run (recurse)
# suspend (yield) to continue executing from the stack
push(peek() - 1)
push(self)
swap2()
push(fib())
yield
# stack now has fib(n-1) and arg, swap them to bring arg to the top
swap2()
# then do the same again for n-2
push(peek() - 2)
push(self)
swap2()
push(fib())
yield
# bring the arg to the top again, and discard it
swap2()
pop()
# add the two results, putting the sum back on the stack
push(pop() + pop())
# done. fib(n) is now the top of the stack (the return value)
swap2()
yield
```

The stack shown over time gets a more interesting shape than just a pyramid like is the case with single recursion.

```
[7, 'fib']
[7, 'fib', 6, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 3, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 2, 'fib']
[7, 'fib', 6, 5, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 2, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 1, 'fib']
[7, 'fib', 5, 6, 3, 'fib']
[7, 8, 'fib']
[8, 7, 'fib', 5, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 2, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 1, 'fib']
[8, 7, 'fib', 5, 3, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 1, 3, 'fib', 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 1, 3, 1, 'fib']
[8, 7, 'fib', 3, 5, 2, 'fib']
[8, 7, 5, 'fib']
13
```

I suppose one might want to display something other than ‘fib’ since the fibs are in different locations in the fib routine, but I think it’s fine if it is read as “resume fib”