Problem 4: Insect Combinatorics (200pts)

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 by one step (e.g., from (0, 0) to (0, 1) or (1, 0)).

Write a function paths that takes as input a grid's length M and width N, then paths is supposed to return 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, a 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For a 3 by 3 grid, the insect has 6 different 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 ***"