Using list for stack synthesis for recursion in Python? Examples?

Question

For example, this is my factorial function:

def fact(n): if n<=1: return 1 else: return n*fact(n-1) 

But it falls when n is too large. I would like to emulate this same function using stack emulation. How do I do something like this? What if it's not tail recursion? It’s not easy to find an explanation.

Answer 1

First, you can make the tail recursive:

 def tfact(n,acc=1): if n<=1: return acc else: return tfact(n-1,acc*n) 

But for a more direct translation:

 def ifact(n): stack = [] while True: if n==1: while stack: n *= stack.pop() break else: stack.append(n) n -= 1 return n