从经典问题学递归3X4的方格-从左上角A走到右下角B-只能向右向下走-一共有多少种走法

题目：3X4 的方格 从左上角 A 走到右下角 B 只能向右向下走 一共有多少种走法？

图形：题目转化为图形之后就是，从 (1, 1) 方格走到 (3, 4) 方格有多少种方案（每次走一格）？

分析：
1、根据题目我们知道只能往右走或者向下走，那么从 (2，4) 格子走到 (3，4) 格子只有一种方案，从 (3，3) 格子走到 (3，4) 格子也只有一种方案。
2、以此类推，到某个格子 A 的走法 = A 上面的格子走法 + A 左边的格子走法；
3、如果碰到第一行或者第一列的格子，那么走法只有一种
4、如果碰到第一个格子，我们认为不需要走，即走法为 0

总结：
1、这种把一个复杂的问题分解成若干个有相同规律的子问题的方法，我们称之为递归。
2、递归由递归条件和递归出口组成，其中递归出口非常重要。
3、分析中的第 2 点我们称之为递归条件。
4、分析中的点 3、4 点我们称之为递归出口（返回明确的值）。

代码：

// N X M 的方格 从左上角 A(1, 1)走到右下角 B(N, M) 只能向右向下走 一共有多少种走法？function calc(x, y){// 坐标(1, 1)  递归出口
    if(x == 1 && y == 1) return 0;

    // 坐标(x, 1) (1, y) 递归出口
    if(x == 1 || y == 1) return 1;
    
    // 递归条件
    if(x > 1 && y > 1) {return calc(x-1, y) + calc(x, y-1);
    }
       
    // 不符合条件，直接返回 0
    return 0;
}

calc(3, 4); // 10

问题：
根据上面的分析，我们知道在递归的过程中，会有很多重复的格子，非常浪费性能，当计算的数字越大，递归的性能也会越低，怎么提高递归的性能呢？下次我们再介绍（剪枝）。