recursive problem

[sam]

A litte while ago somebody on this group asked about a problem at this
site:

http://www.itasoftware.com/careers/programmers.php

I've been looking at the "mystery M function" question, just for fun,
I'm not going for a job there (honest). Below is the code of where
i've got to but it blows becuase it goes too deep into recursion I
think (for i,j,k = 4,4,4 anyway). What I'm doing here is storing in a
Dictionary the result of m where I get one, so I can use it later. As
I said it still blows. Any clues for how to improve my algorithm
appriciated.


Python code:


import sys
import string

dict = {}
count = 0

def m(i, j, k):
    print "i, j, k", i, j, k
    returne = 0
    key = "%i_%i_%i" % (i, j, k)
    if (dict.has_key(key)):
        returne = dict[key]
        global count
        count = count + 1
        print count, " USING DICT"
    else:
        if (i == 0): returne = 1+k
        elif (i ==1 and k == 0):returne = j
        elif (i == 2 and k == 0):returne = 0
        elif (k == 0):returne = 1
        else: returne = m(i-1, j, m(i, j, (k-1)))
        dict[key] = returne
    return returne        
        

if __name__=='__main__':
    print "Start ..."
    print m(4, 4, 4)