Using a list to synthesize a stack for recursion in Python? Examples?

Question

For instance, this is my factorial function:

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

But it crashes when n is too high. I'd like to emulate this exact same function using a stack emulation. How would I do something like this? What if it's not tail-recursive? Having a hard time finding explanations.

Scott Hunter · Accepted Answer · 2011-12-07 15:10:24Z

4

First off, you could make it 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

answered Dec 7, 2011 at 15:10

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Using a list to synthesize a stack for recursion in Python? Examples?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related