How to convert a recursive function to a non recursive one using stack while keeping memoization?

Question

Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.

I could simply count it using a recursive function as follows:

def num_ways(s: str) -> int:
    if len(s) > 0 and s[0] == '0':
        return 0

    if len(s) <= 1:
        return 1

    if len(s) >= 2 and int(s[:2]) > 26:
        return num_ways(s[1:])
    
    return num_ways(s[1:]) + num_ways(s[2:])

However, this function can be easily optimized by using memoization technique. (I'll avoid showing off memoization into that code to keep it tidy, but you can assume I could use such a decorator that would be responsible for this job)

Alright! But what if I want to use a stack to replace that recursion? (I don't want to use a bottom-up dynamic programming approach in this case)

So I could have something like this:

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)
    
    ways = 0
    while stack:
        cur_s = stack.pop()

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        stack.append(cur_s[1:])
        stack.append(cur_s[2:])
        
    return ways

It works! But how can I optimize it by memoizing duplicate work as well as I'm able to do in the recursive method? Moreover, is there a better way to convert from a recursive function to a stack-based non-recursive one?

Answer 1

You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.

Additionally, you also need to check whether the table already contains the entry when you add an item to the stack; this avoids blowing up the stack with already memoized entries.

maintain a hashtable T of strings.

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)
    
    ways = 0
    while stack:
        cur_s = stack.pop()
        if cur_s is in T, then discard cur_s and continue

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        if cur_s[1:] is not in T:
            stack.append(cur_s[1:])
        if cur_s[2:] is not in T:
        stack.append(cur_s[2:])
        
    return ways

To answer your second question, which is if there are other methods of converting recursion to iteration, there certainly is. For certain functions that are tail-recursive (and if not, you can try rewriting them into tail-recursive ones using continuous-passing style) you can convert them to equivalent iterative algorithms without keeping a stack but a bunch of variables.

For dynamic programming recurrences, the conventional practice for iterative computation is you identify an order which can be used to correctly fill up the memoization table (e.g. row-major, column-major, or diagonal) and use nested loops to iteratively compute the values in the memoization table. This potentially saves space, as it avoids the need to maintain a stack during the recursion.