（java实现）

题目描述：

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

本题含有多组样例输入。

输入描述：

每组样例输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述：

每组样例输出一行结果
示例1：

输入

2 2
1 2

输出

6
3

问题分析：

使用递归来实现，将右下角看做原点(0, 0)，左上角看做坐标(m, n)。
从(m, n)—>(0, 0)就分两步走：
往右走一步：f(m, n - 1)—>(0, 0) ，往下走一步：f(m - 1, n)—>(0, 0)；
注意：但凡是触碰到边界，也就是说f(x, 0)或者f(0,x)都只有一条直路可走了，这里的x为变量。
f(m, n) = f(m, n - 1) + f(m - 1, n)

相关知识：

略

参考代码：

import java.util.*;
public class Main {
    //  use recursion
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            int n = input.nextInt();
            int m = input.nextInt();
            int sum = getRecursion(n,m);
            System.out.println(sum);
        }
    }

    public static int getRecursion(int n, int m)
    {
        if (0==n || 0==m)
        {
            return 1;
        }
        return getRecursion(n-1,m)+getRecursion(n,m-1);
    }
}