A mobile readable version of `stackify` https://gist.github.com/razimantv/1b33d4a090a5bc9ed94928012b37c3f0

stackify.py

class stackify(object):
    """Wrapper for stack-based recursion with memoisation
    
    When the function is called and argument is not in cache, push it to stack
    Attempt to call the function on the arguments in the stack such that an
    exception is raised if the function tries to recurse. In that case, add the
    function argument to the stack and continue
    
    The order of successful arguments also provides a topological sort

    Warning:
        1. Works only for "pure" side-effect-free functions without cycles
        2. Immoral use of exceptions
    
    Attributes:
        __cache: Dictionary to memoise based on string representation of args
        __primary: Flag to denote whether we are in a primary function call
        toposort: Topological sort of the states of the function
        log: Flag whether logging is required. Default: False
        sort: Flag whether topological sort is required. Default: False
    """
    def __init__ (self, f):
        self.__f = f
        self.__cache = {}
        self.__primary = True
        self.toposort = []
        self.log = False
        self.sort = False
    
    def __call__(self, *args):
        # Before calling the function, check if the argument is present in cache
        key=str(args)
        if key in self.__cache:
            return self.__cache[key]
        
        if self.__primary:
            # We are in a direct call. Initialise the stack
            if self.log: print('Primary call on ' + str(args))
            self.__primary = False
            self.__stack = [args]
            if self.log: print('Push ' + str(args) + ' to stack')
            while len(self.__stack) > 0:
                # Pop an element from the stack and attempt to call the function
                arg = self.__stack.pop()
                if self.log: print('Pop ' + str(arg) + ' from stack')
                try:
                    if self.log: print('Attempt to call ' + str(arg))
                    value = self.__f(*arg)
                    
                    # If an exception has not been raised, we have successful evaluation
                    # We are guaranteed that any state the f(arg) needs is already
                    # present in toposort[], so add arg to the toposort
                    if self.sort: self.toposort.append(arg)
                    if self.log: print('Attempt to call ' + str(arg) + ' successful')
                    self.__cache[str(arg)] = value
                except:
                    # Tried to recurse to non-cached value
                    # Push it to stack after previous argument
                    if self.log: print('Attempt to call ' + str(arg) + ' failed')
                    self.__stack.append(arg)
                    self.__stack.append(self.__nextarg)
                    if self.log: print('Push ' + str(arg) + ' to stack')
                    if self.log: print('Push ' + str(self.__nextarg) + ' to stack')
            self.__primary = True
            
            # We are guaranteed that the original argument was evaluated last
            # So we can just return the value
            return value
        else:
            # Tried to recurse to non-cached value
            # Save the argument and crash
            if self.log: print('Attempted secondary call on ' + str(args))
            self.__nextarg = args
            raise Exception()

usage.py

from stackify import stackify

@stackify
def fib(N):
    if N<2: return 1
    return (fib(N-2) + fib(N-1))%1000000007

# This would crash if we were doing memoised recursion without stackify
fib(1000000)
# returns 534400663

@stackify
def ackermann(M,N):
    if M == 0: return N+1
    if N == 0: return ackermann(M-1,1)
    return ackermann(M-1, ackermann(M,N-1))

# Show call sequence and topological sort of states for Ackermann function
ackermann.log = True
ackermann.sort = True
ackermann(1,4)
ackermann.toposort

''' Logs 
Primary call on (1, 4)
Push (1, 4) to stack
Pop (1, 4) from stack
Attempt to call (1, 4)
Attempted secondary call on (1, 3)
Attempt to call (1, 4) failed
Push (1, 4) to stack
Push (1, 3) to stack
Pop (1, 3) from stack
Attempt to call (1, 3)
Attempted secondary call on (1, 2)
Attempt to call (1, 3) failed
Push (1, 3) to stack
Push (1, 2) to stack
Pop (1, 2) from stack
Attempt to call (1, 2)
Attempted secondary call on (1, 1)
Attempt to call (1, 2) failed
Push (1, 2) to stack
Push (1, 1) to stack
Pop (1, 1) from stack
Attempt to call (1, 1)
Attempted secondary call on (1, 0)
Attempt to call (1, 1) failed
Push (1, 1) to stack
Push (1, 0) to stack
Pop (1, 0) from stack
Attempt to call (1, 0)
Attempted secondary call on (0, 1)
Attempt to call (1, 0) failed
Push (1, 0) to stack
Push (0, 1) to stack
Pop (0, 1) from stack
Attempt to call (0, 1)
Attempt to call (0, 1) successful
Pop (1, 0) from stack
Attempt to call (1, 0)
Attempt to call (1, 0) successful
Pop (1, 1) from stack
Attempt to call (1, 1)
Attempted secondary call on (0, 2)
Attempt to call (1, 1) failed
Push (1, 1) to stack
Push (0, 2) to stack
Pop (0, 2) from stack
Attempt to call (0, 2)
Attempt to call (0, 2) successful
Pop (1, 1) from stack
Attempt to call (1, 1)
Attempt to call (1, 1) successful
Pop (1, 2) from stack
Attempt to call (1, 2)
Attempted secondary call on (0, 3)
Attempt to call (1, 2) failed
Push (1, 2) to stack
Push (0, 3) to stack
Pop (0, 3) from stack
Attempt to call (0, 3)
Attempt to call (0, 3) successful
Pop (1, 2) from stack
Attempt to call (1, 2)
Attempt to call (1, 2) successful
Pop (1, 3) from stack
Attempt to call (1, 3)
Attempted secondary call on (0, 4)
Attempt to call (1, 3) failed
Push (1, 3) to stack
Push (0, 4) to stack
Pop (0, 4) from stack
Attempt to call (0, 4)
Attempt to call (0, 4) successful
Pop (1, 3) from stack
Attempt to call (1, 3)
Attempt to call (1, 3) successful
Pop (1, 4) from stack
Attempt to call (1, 4)
Attempted secondary call on (0, 5)
Attempt to call (1, 4) failed
Push (1, 4) to stack
Push (0, 5) to stack
Pop (0, 5) from stack
Attempt to call (0, 5)
Attempt to call (0, 5) successful
Pop (1, 4) from stack
Attempt to call (1, 4)
Attempt to call (1, 4) successful
'''

''' Returns
[(0, 1),
 (1, 0),
 (0, 2),
 (1, 1),
 (0, 3),
 (1, 2),
 (0, 4),
 (1, 3),
 (0, 5),
 (1, 4)]
'''