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?

• greybeard: (Check out CodeReview@SE.)
• D.W.: Cross-posted: cs.stackexchange.com/q/129681/755, stackoverflow.com/q/63648207/781723. Please do not post the same question on multiple sites.
• ggorlen: @greyboard No, this would be a poor fit for Code Review. OP is not looking to get open-ended feedback on their code, they're looking to implement new functionality. Please see on topic and don't ask.

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.

• Yago Tomé: thanks for your answer! However, using a hash table to memoize an already computed string requires to keep track of the number of ways that particular string has. How would you do it? I didn't get how you'd fill the hash table.
• BearAqua the Logician: @YagoTomé Not sure I understand you r question. You initialize a hash table, and then gradually fill it out using the procedure described above. This allows you to avoid repeated computation.
• BearAqua the Logician: The tables don't have to be of fixed size, or you can use something like a trie to store the string arguments.
• Yago Tomé: I mean for example if cur_s is '111', I'd need to have an entry like '111' => 3 since there're 3 ways of decoding 111 (aaa, ak, ka). However, in this stack-based code I only have the solution for strings whose length is 1 (or those which start with 27+). So how can I keep track of the relation num_ways(s) = num_ways(s[1:]) + num_ways(s[2:]) using that hash table?
• ggorlen: I agree with OP, this pseudocode never shows anything being added to the hash table and feels incomplete. The point of memoization is that as the call stack unwinds, the memoization table is populated which enables the avoidance of future repeated computations.