Count the number of possible paths through a grid

There is a robot at the top-left corner of an N*M grid. The robot can move up, down, left and right, but cannot visit the same cell more than once in each traversal. How do I find the total number of ways the robot can reach the bottom-right corner?

(the robot does not need to visit every cell for a path to be valid)

I think there is a recursive solution to this but I can't get it somehow.

Here's what I've got so far:

def initialize(row, cols):
    grid = [ [ 0 for c in range(cols) ] for r in range(rows) ]
    pos_r, pos_c = 0, 0
    grid[pos_r][pos_c] = 1 # set start cell as visited
    dst_x, dst_y = len(grid)-1, len(grid[0])-1 # coords of bottom-right corner
    print move_robot(grid, dst_x, dst_y, pos_r, pos_c)

def move_robot(grid, dst_x, dst_y, pos_r, pos_c, prev_r=None, prev_c=None):
    num_ways = 0
    if reached_dst(dst_x, dst_y, pos_r, pos_c):
        undo_move(grid, pos_r, pos_c)
        undo_move(grid, prev_r, prev_c)
        return 1
    else:
        moves = get_moves(grid, pos_r, pos_c)
        if len(moves) == 0:
            undo_move(grid, prev_r, prev_c)
            return 0
        for move in moves:
            prev_r = pos_r
            prev_c = pos_c
            pos_r = move[0]
            pos_c = move[1]
            update_grid(grid, pos_r, pos_c)
            num_ways += move_robot(grid, dst_x, dst_y, pos_r, pos_c, prev_r, prev_c)
    return num_ways

if __name__ == '__main__':
    initialize(4, 4)

I left out some function definitions for brevity. Get_moves retrieves the all legal moves, checking whether each move would still be on the board and whether the cell has already been visited. Update_grid sets the specified cell to '1', which means visited. Undo_move does the opposite, setting the specified cell to '0'.

I get the right answer for the simplest possible case (2*2 grid), but for larger grids the output is always too low. What's wrong with my code, and is there a simpler way of doing this?