Practice Tree Recursion

Q3: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (1, 1), and wants to end up at the top right corner, (M, N). 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 different paths 

Hint: What happens if we hit the top or rightmost edge?

문제 이해하기

• path함수 작성
• grid의 length, width를 매개변수로 받고
• 서로 다른 경로의 수를 리턴
• 재귀를 사용해서 풀어라

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
    """
    # m if length, n is width
    path_num = 0
    if m == 1 or n == 1:
        return 1
    return paths(m-1, n) + paths(m, n-1)