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.

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