You've probably been told that you can convert any recursive function into an iterative loop just by using an explicit stack.

Tail-recursive functions

Whenever you get an example, it's usually something that's trivial, because the function was tail-recursive, so you don't even need a stack:

    def fact(n, value=1):
        if n<2:
            return 1
        return fact(n-1, value*n)
That maps directly to:
    def fact(n):
        value = 1
        while True:
            if n<2:
                return value
            n, value = n-1, value*n
You can merge the while and if, at which point you realize you have a for in disguise. and then you can realize that, multiplication being commutative and associative and all that, you might as well turn the loop around, so you get:
    def fact(n):
        value = 1
        for i in range(2, n+1):
            value *= i
        return value
(You might also notice that this is just functools.reduce(operator.mul, range(2, n+1), 1), but if you're the kind of person who notices that and finds it more readable, you probably also rewrote the tail-recursive version into a recursive fold/reduce function, and all you had to do was find an iterative reduce function to replace it with.)

Continuation stacks

Your real program isn't tail-recursive. Either you didn't bother making that transformation because your language doesn't do tail call elimination (Python doesn't), or the whole reason you're switching from recursive to iterative in the first place is that you couldn't figure out a clean way to write your code tail-recursively.

So, now you need a stack. But what goes on the stack?

The most general answer to that is that you want continuations on the stack: what the result of the function does with the result of each recursive call. That may sound scary, and in general it is… but in most practical cases, it's not.

Let's say you have this:
    def fact(n):
        if n < 2:
            return 1
        return n * fact(n-1)
What's the continuation? It's "return n * _", where that _ is the return value of the recursive call. You can write a function with one argument that does that. (What about the base case? Well, a function of 1 argument can always ignore its argument). So, instead of storing continuations, you can just store functions:
    def fact(n):
        stack = []
        while True:
            if n < 2:
                stack.append(lambda _: 1)
                break
            stack.append(lambda _, n=n: _ * n)
        value = None
        for frame in reversed(stack):
            value = frame(value)
        return value
(Notice the n=n in the second lambda. See the Python FAQ for an explanation, but basically it's to make sure we're building a function that uses the current value of n, instead of one that closes over the variable n.)

This is undeniably kind of ugly, but we can start simplifying it. If only the base case and the recursive call had the same form, we could factor out the whole function, right? Well, if we start with 1 instead of None, the base case can return _ * 1. And then, yes, we can factor out the whole function, and just store each n value on the stack:
    def fact(n):
        stack = []
        while True:
            if n < 2:
                stack.append(1)
                break
            stack.append(n)
        value = 1
        for frame in reversed(stack):
            value = value * frame
        return value
But once we're doing this, why even store the 1? And, once you take that out, the while loop is obviously a for loop over a range in disguise:
    def fact(n):
        stack = []
        for i in range(n, 1, -1):
            stack.append(i)
        value = 1
        for frame in reversed(stack):
            value *= frame
        return value
Now stack is obviously just list(range(n, 1, -1)), so we can skip the loop entirely:
    def fact(n):
        stack = list(range(n, 1, -1))
        value = 1
        for frame in reversed(stack):
            value *= frame
        return value
Now, we don't really care that it's a list, as long as it's something we can pass to reversed. In fact, why even call reversed on a backward range when we can just write a forward range directly?
    def fact(n):
        value = 1
        for frame in range(2, n+1):
            value *= frame
        return value
Not surprisingly, we ended up with the same function we got from the tail recursive starting point.

Interpreter stacks

Is there a way to do this in general without stacking up continuations? Of course there is. After all, an interpreter doesn't have to call itself recursively just to execute your recursive call (even if CPython does, Stackless doesn't…), and your CPU certainly isn't calling itself recursively to execute compiled recursive code.

Here's what a function call does: The caller pushes the "program counter" and the arguments onto the stack, then it jumps to the callee. The callee pops, computes the result, pushes the result, jumps to the popped counter. The only issue is that the callee can have locals that shadow the caller's; you can handle that by just pushing all of your locals (not the post-transformation locals, which include the stack itself, just the set used by the recursive function) as well.

This sounds like it might be hard to write without a goto, but you can always simulate goto with a loop around a state machine. So:

    State = enum.Enum('State', 'start cont done')

    def fact(n):
        state = State.start
        stack = [(State.done, n)]
        while True:
            if state == State.start:
                pc, n = stack.pop()
                if n < 2:
                    # return 1
                    stack.append(1)
                    state = pc
                    continue
                # stash locals
                stack.append((pc, n))
                # call recursively
                stack.append((State.cont, n-1))
                state = State.start
                continue
            elif state == State.cont:
                # get return value
                retval = stack.pop()
                # restore locals
                pc, n = stack.pop()
                # return n * fact(n-1)
                stack.append(n * retval)
                state = pc
                continue
            elif state == State.done:
                retval = stack.pop()
                return retval
Beautiful, right? Well, we can find ways to simplify this. Let's start by using one of the tricks native-code compilers use: in addition to the stack, you've also got registers. As long as you've got enough registers, you can pass arguments in registers instead of on the stack, and you can return values in registers too. And we can just use local variables for the registers. So:
    def fact(n):
        state = State.start
        pc = State.done
        stack = []
        while True:
            if state == State.start:
                if n < 2:
                    # return 1
                    retval = 1
                    state = pc
                    continue
                stack.append((pc, n))
                pc, n, state = State.cont, n-1, State.start
            elif state == State.cont:
                state, n = stack.pop()
                retval = n * retval
            elif state == State.done:
                return retval
1

View comments

  1. The code for the first recursion is wrong. The base condition, if n<2 needs to return value, to get the recursion working.

    ReplyDelete
Hybrid Programming
Hybrid Programming
5
Greenlets vs. explicit coroutines
Greenlets vs. explicit coroutines
6
ABCs: What are they good for?
ABCs: What are they good for?
1
A standard assembly format for Python bytecode
A standard assembly format for Python bytecode
6
Unified call syntax
Unified call syntax
8
Why heapq isn't a type
Why heapq isn't a type
1
Unpacked Bytecode
Unpacked Bytecode
3
Everything is dynamic
Everything is dynamic
1
Wordcode
Wordcode
1
For-each loops should define a new variable
For-each loops should define a new variable
4
Views instead of iterators
Views instead of iterators
2
How lookup _could_ work
How lookup _could_ work
2
How lookup works
How lookup works
7
How functions work
How functions work
2
Why you can't have exact decimal math
Why you can't have exact decimal math
2
Can you customize method resolution order?
Can you customize method resolution order?
1
Prototype inheritance is inheritance
Prototype inheritance is inheritance
1
Pattern matching again
Pattern matching again
The best collections library design?
The best collections library design?
1
Leaks into the Enclosing Scope
Leaks into the Enclosing Scope
2
Iterable Terminology
Iterable Terminology
8
Creating a new sequence type is easy
Creating a new sequence type is easy
2
Going faster with NumPy
Going faster with NumPy
2
Why isn't asyncio too slow?
Why isn't asyncio too slow?
Hacking Python without hacking Python
Hacking Python without hacking Python
1
How to detect a valid integer literal
How to detect a valid integer literal
2
Operator sectioning for Python
Operator sectioning for Python
1
If you don't like exceptions, you don't like Python
If you don't like exceptions, you don't like Python
2
Spam, spam, spam, gouda, spam, and tulips
Spam, spam, spam, gouda, spam, and tulips
And now for something completely stupid…
And now for something completely stupid…
How not to overuse lambda
How not to overuse lambda
1
Why following idioms matters
Why following idioms matters
1
Cloning generators
Cloning generators
5
What belongs in the stdlib?
What belongs in the stdlib?
3
Augmented Assignments (a += b)
Augmented Assignments (a += b)
11
Statements and Expressions
Statements and Expressions
3
An Abbreviated Table of binary64 Values
An Abbreviated Table of binary64 Values
1
IEEE Floats and Python
IEEE Floats and Python
Subtyping and Ducks
Subtyping and Ducks
1
Greenlets, threads, and processes
Greenlets, threads, and processes
6
Why don't you want getters and setters?
Why don't you want getters and setters?
8
The (Updated) Truth About Unicode in Python
The (Updated) Truth About Unicode in Python
1
How do I make a recursive function iterative?
How do I make a recursive function iterative?
1
Sockets and multiprocessing
Sockets and multiprocessing
Micro-optimization and Python
Micro-optimization and Python
3
Why does my 100MB file take 1GB of memory?
Why does my 100MB file take 1GB of memory?
1
How to edit a file in-place
How to edit a file in-place
ADTs for Python
ADTs for Python
5
A pattern-matching case statement for Python
A pattern-matching case statement for Python
2
How strongly typed is Python?
How strongly typed is Python?
How do comprehensions work?
How do comprehensions work?
1
Reverse dictionary lookup and more, on beyond z
Reverse dictionary lookup and more, on beyond z
2
How to handle exceptions
How to handle exceptions
2
Three ways to read files
Three ways to read files
2
Lazy Python lists
Lazy Python lists
2
Lazy cons lists
Lazy cons lists
1
Lazy tuple unpacking
Lazy tuple unpacking
3
Getting atomic writes right
Getting atomic writes right
Suites, scopes, and lifetimes
Suites, scopes, and lifetimes
1
Swift-style map and filter views
Swift-style map and filter views
1
Inline (bytecode) assembly
Inline (bytecode) assembly
Why Python (or any decent language) doesn't need blocks
Why Python (or any decent language) doesn't need blocks
18
SortedContainers
SortedContainers
1
Fixing lambda
Fixing lambda
2
Arguments and parameters, under the covers
Arguments and parameters, under the covers
pip, extension modules, and distro packages
pip, extension modules, and distro packages
Python doesn't have encapsulation?
Python doesn't have encapsulation?
3
Grouping into runs of adjacent values
Grouping into runs of adjacent values
dbm: not just for Unix
dbm: not just for Unix
How to use your self
How to use your self
1
Tkinter validation
Tkinter validation
7
What's the deal with ttk.Frame.__init__(self, parent)
What's the deal with ttk.Frame.__init__(self, parent)
1
Does Python pass by value, or by reference?
Does Python pass by value, or by reference?
9
"if not exists" definitions
"if not exists" definitions
repr + eval = bad idea
repr + eval = bad idea
1
Solving callbacks for Python GUIs
Solving callbacks for Python GUIs
Why your GUI app freezes
Why your GUI app freezes
21
Using python.org binary installations with Xcode 5
Using python.org binary installations with Xcode 5
defaultdict vs. setdefault
defaultdict vs. setdefault
1
Lazy restartable iteration
Lazy restartable iteration
2
Arguments and parameters
Arguments and parameters
3
How grouper works
How grouper works
1
Comprehensions vs. map
Comprehensions vs. map
2
Basic thread pools
Basic thread pools
Sorted collections in the stdlib
Sorted collections in the stdlib
4
Mac environment variables
Mac environment variables
Syntactic takewhile?
Syntactic takewhile?
4
Can you optimize list(genexp)
Can you optimize list(genexp)
MISRA-C and Python
MISRA-C and Python
1
How to split your program in two
How to split your program in two
How methods work
How methods work
3
readlines considered silly
readlines considered silly
6
Comprehensions for dummies
Comprehensions for dummies
Sockets are byte streams, not message streams
Sockets are byte streams, not message streams
9
Why you don't want to dynamically create variables
Why you don't want to dynamically create variables
7
Why eval/exec is bad
Why eval/exec is bad
Iterator Pipelines
Iterator Pipelines
2
Why are non-mutating algorithms simpler to write in Python?
Why are non-mutating algorithms simpler to write in Python?
2
Sticking with Apple's Python 2.7
Sticking with Apple's Python 2.7
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.