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]

Answer 2

How about something like (built code on fly, so sorry for any typos/bugs):

def collatz_generator(n):
    while n != 1:
        n = n & 1 and (3 * n + 1) or n / 2
        yield n

def add_sequence_to_table(n, table):
    table = table or {1:1}
    sequence = list(collatz_generator(n))
    reversed = list(enumerate(sequence))[::1]

    for len, num in reversed:
        if num in table:
            break
        table[n] = len + 1
    return table

def build_table(n):
    table = add_sequence_to_table(2)
    for n in xrange(3, n):
        table = add_sequence_to_table(n, table)

    return table

Without building table (typed on fly as wife wants me to get read):

def without_table(n):
    max_l, examined_numbers = 0, set()
    for x in xrange(2, n):
        reversed = list(enumerated(collatz_generator(x)))[::-1]
        for num, length in reversed:
            if num in examined_numbers:
                break

            examined_numbers.add(num)

            if num <= n:  # I think this was a problem requirement.
                max_l = max(max_l, length)

Doesn't this work?