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

Question

求大神讲解一下 两个递归自己调自己是怎么执行的。跪求！！！

function go($x, $y)
{ 
    if ($x == 0 && $y == 0) { 
        return 0;
    } else if ($x == 0 || $y == 0) { 
        return 1;
    } 

    $result = go($x, $y - 1) + go($x - 1, $y); 
    return  $result;
}

echo go(3, 4);

https://blog.csdn.net/qq_3363...

Answer 1

首先这个写法是有误的，原点应该是第一行第一列，也就是 x=1,y=1，而不是x=0,y=0；
比如你去第二行第二列，上面答案是6，实际上就两种走法；

function go($x, $y)
{
    if ($x == 1 && $y == 1) {
        return 0;
    } else if ($x == 1 || $y == 1) {
        return 1;
    }

    $result = go($x, $y - 1) + go($x - 1, $y);
    return  $result;
}

echo go(3, 4);

这个是简单的经典递归算法；

可以把” 递归 “比喻成 “查字典 “，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。
可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思（摘抄）；

return 是终止条件，终止之后层层返回，以这个为例：
如果x=1,y=1时表示已经到原点了，没有路线了返回0；
如果x或者y等于1，表示任意到达一个边，这时只剩一种走法，返回1；

递归需要自己理解，多多练习，另外不要试图去还原极深层次的运算流程，因为它是相同运算逻辑的循环，你只需要明白两层即可；

希望下面的运算可以帮助你理解：

echo go(3, 3);

/**
 * 以第三行，第三列为例：
 *      go(3, 3)；获取下层结果： 6
 *          go(3, 2)；return 3;                                                          + go(2, 3)；return 3;
 *              go(3, 1)；return 1；+ go(2, 2) return 2 ; = 3                                 go(2, 2)；return 1；+ go(1, 3) return 2 ; = 3
 *                           go(2, 1)；return 1； +  go(1, 2) return 1；= 2；                       go(2, 1)；return 1； +  go(1, 2) return 1；= 2；
 * 遇到go会先往深层调用，遇到return才层层返回；
 */

Answer 2

Answer 3

所以这里为什么要用递归的写法？

Answer 4

根据您的问题我写了一篇文章，有详细的介绍：https://segmentfault.com/a/11...

Answer 5

这是经典的动态规划问题，用动态规划，比递归要好，递归还要考虑递归深度的问题