Replace arbitrary recursion with a stack?
It seems obvious that recursion is implemented using stacks. But how was general recursion implemented using the stack in general? For example, if we have a user-defined function that is recursive, can we rewrite the code using only stack and iteration?
Here's one example (I gave the wrong example in another post):
def recursiveCall(node):
if node==None:
return (0,True)
(left,lstatus) = recursiveCall(node.left)
(right,rstatus) = recursiveCall(node.right)
if lstatus==True and rstatus==True:
if abs(left-right)<=1:
return (max(left,right)+1,True)
else:
return (0,False)
else:
return (0,False)
or simpler:
def recursiveInorder(node):
if node==None:
return
recursiveInorder(node.left)
print(node.val)
recursiveInorder(node.right)
how do you understand this recursion using stacks? Please note that I am not asking for an iterative solution to the above two examples. I believe it should be. But I suppose these iterative solutions are not trying to replicate the recursion mechanism using a stack. I would like to see, if possible, these recursions can be completely replaced with a custom coded stack mechanism (basically creating an implicit recursion mechanism built into the compiler or something explicitly).
I think I need to find a way to track and restore program status, local variables, etc.? THX.
node class is defined as:
class node:
def __init__(self,x):
self.val=x
self.left=None
self.right=None
source to share
Basically, when simulating a recursive call, you need to push on the local variables of the stack and the point at which execution should resume after returning.
I'll point out the relevant execution points with numbered comments here. Think of them as labels goto
.
def recursiveInorder(node):
#0
if node==None:
return
recursiveInorder(node.left)
#1
print(node.val)
recursiveInorder(node.right)
#2
return
Now we can use the operator if-elif
to model expressions goto
:
def in_order(node):
stack = [(None, None)] #sentinel
goto = 0
while stack:
if goto == 0:
if node is None:
#return
(node, goto) = stack.pop()
else:
#push state and recurse left
stack.append((node, goto+1))
(node, goto) = (node.left, 0)
elif goto == 1:
print(node.val)
#push state and recurse right
stack.append((node, goto+1))
(node, goto) = (node.right, 0)
else:
#return
(node, goto) = stack.pop()
It will output at the end (None, None)
, but the values will never be used since the loop ends while
.
The above code is the result of a simple conversion. We can then apply various optimizations to keep things simple.
The last branch is else
not doing useful work. We can remove it if we also remove the click, which will take us there.
def in_order(node):
stack = [(None, None)] #sentinel
goto = 0
while stack:
if goto == 0:
if node is None:
#return
(node, goto) = stack.pop()
else:
#push state and recurse left
stack.append((node, goto+1))
(node, goto) = (node.left, 0)
else:
print(node.val)
#recurse right
(node, goto) = (node.right, 0)
Now the value goto
that popped the stack is always 1. We only need to push node
on the stack and assign goto = 1
when popped from the stack.
def in_order(node):
stack = [None] #sentinel
goto = 0
while stack:
if goto == 0:
if node is None:
#return
(node, goto) = (stack.pop(), 1)
else:
#push state and recurse left
stack.append(node)
(node, goto) = (node.left, 0)
else:
print(node.val)
#recurse right
(node, goto) = (node.right, 0)
If we change the inner if
to a loop while
...
def in_order(node):
stack = [None] #sentinel
goto = 0
while stack:
if goto == 0:
while node is not None:
#push state and recurse left
stack.append(node)
node = node.left
#return
(node, goto) = (stack.pop(), 1)
else:
print(node.val)
#recurse right
(node, goto) = (node.right, 0)
... we can see that after each branch of the instruction, if
we want to branch to another branch until the checksum value appears at the end. We can eliminate the goto
and operator if
if we add a check for an empty stack in the middle. If we put the check before the pop, we no longer need the controller on the stack.
def in_order(node):
stack = []
while True:
while node is not None:
stack.append(node)
node = node.left
if stack:
node = stack.pop()
print(node.val)
node = node.right
else:
return
The code now looks clean and simple.
source to share