dotslash
4/15/2016 - 7:36 AM

## Examples for my post on converting recursion to stack

Examples for my post on converting recursion to stack

``````def hanoi(n, fr, to, buf):
if (n == 0):
return
#print "deb", 'l', n, fr, to, buf
hanoi(n-1, fr, buf, to)
#print "deb", 'r', n, fr, to, buf
print "{} {}->{}".format(n, fr, to)
hanoi(n-1, buf, to, fr)

def hanoi_iter(n, fr, to, buf):
stack = list() #python's list can be used as stack
stack.append(('full', n, fr, to, buf))
while len(stack) != 0:
op, n, fr, to, buf = stack.pop()
if n == 0:
continue
#print "deb", op, n, fr, to, buf
if op == 'step1':
print "{} {}->{}".format(n, fr, to)
stack.append(('full', n-1, buf, to, fr))
else:
#saving the state
stack.append(('step1', n, fr, to, buf))
stack.append(('full', n-1, fr, buf, to))

if (len(inp) - start) < k or k < 0:
#invalid
return []
if k == 0:
if (len(inp) - start) == k:
ret.extend(inp[start:])
return [ret]
#Base cases done
#pick k elements in inp[start+1:] and not include inp[start]
without_pres = selectK(inp, k, start+1, to_add)

#step1(of stack solution) starts here
#pick k-1 elements in inp[start+1:] and include inp[start]
with_pres = selectK(inp, k-1, start+1, to_add)

#step2(of stack solution) starts here
ret = with_pres
ret.extend(without_pres)
return ret

def selectK_iter(inp, k):
stack = list()
# 5 elements in the tuple
# (operation, k, start_of_list, to_add, extra_info)
stack.append(('full', k, 0, [], None))
ret = None
while len(stack) != 0:
opn, k, start, to_add, extra = stack.pop()
if opn == 'full':
#base cases; replace returns in recursive version
#with assignments to tmp
if (len(inp) - start) < k or k < 0:
#invalid
ret = []
continue
if k == 0:
#one way to pick no elements;
continue
if (len(inp) - start) == k:
#only k present in the array,
ret.extend(inp[start:])
ret = [ret]
continue
#base cases Done
#save the state
elif opn == 'step1':
else:
with_pres = ret
without_pres = extra
with_pres.extend(without_pres)
ret = with_pres
return ret

print "hanoi size=3"
hanoi(3, 1, 2, 3)
print "hanoi iter size=3"
hanoi_iter(3, 1, 2, 3)
print "========"
print "selectK n=4, k=2"
print '\n'.join(map(str, selectK(range(4), 2)))
print "selectK iter n=4, k=2"
print '\n'.join(map(str, selectK_iter(range(4), 2)))
``````