Iteration vs recursion when dynamic lookup table is required

Question

I was wondering if iteration can be used when using a dynamic lookup table. Using recursion you can get all the necessary lookup table data from bottom to top. I can't seem to grasp how we can achieve the same using iteration, without making a stack and ending up reimplementing the recursion.

For example, take my solution to Project Euler problem #14:

table = {1:1}

def collatz(n):
    if n in table:
        return table[n]
    elif n % 2:
        x = 1 + collatz(3*n + 1)
    else:
        x = 1 + collatz(n/2)
    table[n] = x
    return x

MAXc = 0

for i in xrange(1,1000000):
    temp = collatz(i)
    if temp > MAXc:
        MAXc = temp
        result = i

print result

How could we implement the same using iteration?

Answer 1

An iterative algorithm which just counts the number of steps until reaching 1 is trivial. The problem is to also update the cache for all the intermediate values.

In this particular case there is an iterative algorithm which doesn't require an explicit stack. It uses two passes: the first counts the total number of steps, and the second updates the cache.

def next(n):
    if n % 2 != 0:
        return 3*n + 1
    else:
        return n/2

def collatz(n):
    count = 0
    i = n
    while i not in table:
        count += 1
        i = next(i)
    count += table[i]
    i = n
    while i not in table:
        table[i] = count
        count -= 1
        i = next(i)
    return table[n]