Python: Recursive call counting ways of walking grid yield incorrect answer when grid size is too large

Question

Problem:

Imagine you start at the corner of an X by Y grid. You can only move in two directions: right and down. How many possible paths are there for you to go from (0, 0) to (X, Y)

I have two approaches for this, first is to use a recursive algorithm enhanced by memoization, and the second one is to use binomial counting strategy

Recursive Way

def gridMovingCount(x, y, cache):
    if x == 0 or y == 0:
        return 1
    elif str(x)+":"+str(y) in cache:
        return cache[str(x)+":"+str(y)]
    else:
        cache[str(x)+":"+str(y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) 
        return cache[str(x)+":"+str(y)]

Binomial counting

def gridMovingCountByBinomial(x, y):
    return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))

These two ways give the same answers when x and y are relative small

 #the same result
 print(gridMovingCount(20, 20, cache))    #137846528820
 print(gridMovingCountByBinomial(20, 20)) #137846528820

When x and y are large

# gave different result
print(gridMovingCount(50, 50, cache))    #100891344545564193334812497256
print(gridMovingCountByBinomial(50, 50)) #100891344545564202071714955264

What is the explanation for this. Stack overflow of some sort? However, it does not throw any exception. Are there any way to overcome this for recursive call?

Answer 1

I'm stumped for the time being, but I have some nice progress. I tried a few things to track this:

1. I changed your dictionary key from a string to a tuple (x,y), just to make the code more readable.
2. I added result variables in a few places, to help track returning values.
3. I added several print statements. These track the last corner values of the cache, the results computed in the functions, and the results received.

The new code is below, as is the output. You can see the critical problem in the output: the function does compute the proper value and returns it to the calling program. However, the calling program receives a value that is larger. This happens in Python 3.5.2, but 2.6.6 computes properly. There is also a notation difference: 2.6.6 large values have that trailing "L" on the displayed value.

Code:

import math

def gridMovingCount(x, y, cache):
    if x == 0 or y == 0:
        return 1
    elif (x,y)  in cache:
        if x+y > 98:
          print ("returning cached", x, y, result)
        return cache[(x,y)]
    else:
        cache[(x,y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) # stack will overflow
        result = cache[(x,y)]
        if x+y > 98:
          print ("returning binomial", x, y, result)
        return result

def gridMovingCountByBinomial(x, y):
    return int(math.factorial(x + y) / (math.factorial(x) * math.factorial(y)))


cache={}
#the same result
print(gridMovingCount(20, 20, cache))    #137846528820
print(gridMovingCountByBinomial(20, 20)) #137846528820

# gave different result
print()
print("50x50 summed  ", gridMovingCount(50, 50, cache))    #100891344545564193334812497256
with open("p3.4_out", 'w') as fp:
   lout =  sorted(list(cache.items()))
   for line in lout:
      fp.write(str(line) + '\n')

result = gridMovingCountByBinomial(50, 50)
print()
print("50x50 binomial", result) #100891344545564202071714955264
print("50x50 cached  ", cache[(50,50)])

Output:

$ python3 so.py
137846528820
137846528820

returning binomial 49 50 50445672272782096667406248628
returning binomial 50 49 50445672272782096667406248628
returning binomial 50 50 100891344545564193334812497256
50x50 summed   100891344545564193334812497256

50x50 binomial 100891344545564202071714955264
50x50 cached   100891344545564193334812497256

The difference is 8736902458008; in hex, this is 0x7f237f7aa98 -- i.e. nothing particularly interesting in base 2. It is not a value anywhere in the cache.

I know this isn't a complete answer, but I hope it narrows the problem scope to something that another SO denizen recognizes.

BTW, I diff'ed the cache files; they're identical, except for the trailing 'L' on each long integer in 2.6.6