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

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

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);

clipboard.png

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

阅读 6.2k
5 个回答

首先这个写法是有误的,原点应该是第一行第一列,也就是 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才层层返回;
 */

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

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

推荐问题
宣传栏