Insect combinatorics challenge 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.

    &gt;&gt;&gt; paths(2, 2)
    2
    &gt;&gt;&gt; paths(5, 7)
    210
    &gt;&gt;&gt; paths(117, 1)
    1
    &gt;&gt;&gt; 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.

    &gt;&gt;&gt; paths(2, 2)
    2
    &gt;&gt;&gt; paths(5, 7)
    210
    &gt;&gt;&gt; paths(117, 1)
    1
    &gt;&gt;&gt; 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 &gt; 0:
            find_number_of_paths(x-1, y)
        if y &gt; 0:
            find_number_of_paths(x, y-1)
    find_number_of_paths(m-1, n-1)
    return count_paths  



Can we avoid re-assignment operator on count_paths?
Can we avoid nested function definitions?
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 &gt; 0:
            ret += find_number_of_paths(x-1, y)

        if y &gt; 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 &gt; 1:
        ret += paths(x-1, y)

    if y &gt; 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 &gt; 1:
        ret += paths(x-1, y)

    if y &gt; 1:
        ret += paths(x, y-1)

    _paths_cache[x, y] = ret
    return ret