Insect combinatorics challenge

Question

Below is the problem taken from Berkeley's Cs61A page here

Question 9: Insect Combinatorics*

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"

This solution is with the knowledge of 'higher order function' and 'recursion'. I've yet to learn data structures and algorithms (if required).

Idea: Started from the destination and found the possibilities. As per the skill level, the solution took 3 hours of my time. Please provide feedback on this.

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    count_paths = 0 
    def find_number_of_paths(x, y):
        if x == 0 and y == 0:
            nonlocal count_paths
            count_paths += 1
            return
        if x > 0:
            find_number_of_paths(x-1, y)
        if y > 0:
            find_number_of_paths(x, y-1)
    find_number_of_paths(m-1, n-1)
    return count_paths  

1. Can we avoid re-assignment operator on count_paths?
2. Can we avoid nested function definitions?
3. Is there a name for above solution approach in algorithm world? Any better approach?

Note: As per this assignment, no usage of data model is recommended.

Answer 1

Using nonlocal rather than global is certainly good, but better yet would be returning values.

def paths(m, n):
    def find_number_of_paths(x, y):
        if x == 0 and y == 0:
            return 1

        ret = 0

        if x > 0:
            ret += find_number_of_paths(x-1, y)

        if y > 0:
            ret += find_number_of_paths(x, y-1)

        return ret

    return find_number_of_paths(m-1, n-1)

That lets us elide the outer function entirely:

def paths(x, y):
    if x == 1 and y == 1:
        return 1

    ret = 0

    if x > 1:
        ret += paths(x-1, y)

    if y > 1:
        ret += paths(x, y-1)

    return ret

It's a bit strange to critique this since "no closed-form solution" basically means no good solution. There are ways of speeding this up, though, that avoid that. A trivial one is memoization:

_paths_cache = {(1, 1): 1}
def paths(x, y):
    if (x, y) in _paths_cache:
        return _paths_cache[x, y]

    ret = 0

    if x > 1:
        ret += paths(x-1, y)

    if y > 1:
        ret += paths(x, y-1)

    _paths_cache[x, y] = ret
    return ret