网格路径一共有几种走法

Question

有一个长为M宽为N的网格，从左下角格子出发，每一步只能往上或往右一格，到达右上角网格有多少种走法？
样例输入
3
2
样例输出
3

我的思路是
从m+n步中选出m步向上或n步向右，因此为C(m+n,m)=C(m+n,n)种。
怎么递归呢 感觉不是很简便

Answer 1

因为只能往上和往右，所以就相当于把上方方格的走法和右方方格的走法相加，然后基准方格就是M=1或N=1，任意方向靠边只有一种走法。

def route(m,n):
    if m==1 or n==1:
        return 1
    else:
        return (route(m-1,n) + route(m,n-1))

print(route(3,2))