Louis,

Keep on trying. I'd suggest you start with a smaller version of the problem until you get the bugs worked out. I'd also suggest splitting out sub-parts of your algorithm. You can also time your solutions as you scale up the size of the problem to get an estimate of how your algorithm will perform on the entire original problem.

Good luck,

Eric

Louis,

No, this is not a bug with Mathematica. It's using the memoized values, just as we would expect.

I'm having a hard time mapping your algorithm to that problem, so I'm not sure how to help you correct your algorithm. A brute force method would start from the realizations that any sequence of jumps could produce the croak sequence and for most starting positions there are 2^15 jump sequences, and so finding the probability for that particular croak sequence is a matter of counting the number of occurrences among all of those jump sequences (repeated for each starting point).

So, I'd decompose the algorithm into a function to give me all jump sequences of length N (so I can start smaller than the specified 15), a function to turn those into the associated integers for a given start point, map that across M cells (so I can start smaller than the specified 500), and a function to count occurrences of a target croak sequence (which I will set to simpler test cases in the early phase of developing the algorithm). With this decomposition and complexity reduction, it's easier to correct bugs before attempting the full problem.

But that's a brute force approach...

Louis,

I think you meant "memoized".

I'm pretty sure that one of your g[n - 1, a +- 1, bb, cc] gets evaluated with the same arguments as in a previous step in the recursion. In the case of g, the memoized value is used the second time, but in the case of h, when the same case occurs, it gets recomputed "fresh" rather than looking up a memoized version. It's at that point that g and h diverge.

Maybe tell us the computation you're trying for, and we can suggest a better, more Mathematica-esque approach.

Eric