黑马程序员技术交流社区

标题: 递归的 误区 [打印本页]

---

作者: 孙铭泽    时间: 2012-8-25 21:29
标题: 递归的 误区
裴波那切数列：
* 1,1,2,3,5,8,13,...
*
* 求第二十项的值：
* 规律：第一项和第二项的值都是1，其后每项的值是前两项的和。
}public static int dg(int n) {
                if (n == 1 || n == 2) {
                        return 1;
                } else {
                        return dg(n - 1) + dg(n - 2);
                }
        }
}
（这个函数在执行的时候到最后的  “出口”我没怎么理解过来 求大神帮忙看看  递归是怎么执行的）。

---

作者: 广驰    时间: 2012-8-25 21:33


这个你要是理解栈的概念就很容易理解了，首先这个函数你要求第二十项，那么就传入n=20，这时候dg(20)就压入了栈中，然后判断，执行dg(n-1)也就是dg(19)，把dg(19)压入栈中，继而调用dg()函数传入n=19，继续执行，直到执行到n=1时候的时候，这个时候最后压到栈中的dg(1)就会返回一个结果1
然后给dg(2)，dg(2)又直接返回结果给dg(3)

重点在这里，这个时dg(3)中执行到dg(n - 1) + dg(n - 2)前面的dg(n-1)也就是dg(2)已经有结果返回了，所以开始执行dg(n-2)注意这个时候n的参数是3
因为这时栈顶的就是dg(3)，然后计算右边的dg(n-2)也就是dg(1)，返回结果为1，这个时候，就有dg(3) 的dg(n - 1) + dg(n - 2) 就有结果了，然后就有一个返回值，这个值，被返回给调用者dg(4),然后dg(4)又重复执行压栈操作，知道有结果返回，这样dg(4)出栈，再到dg(5)之后也是一样，一直到栈底的dg(20)计算出结果，这个n=20其实就是出口，

如果你真的看不懂，建议可以把n的值设置为4， 然后自己用手工执行运行一下代码，也就是手动模仿电脑执行，一步步写出来

如果还是不行的话，就找本书，或百度一点点的看吧。最好还是手动的写下每步运行代码

---

作者: 杨震    时间: 2012-8-25 21:37
递归需要自己慢慢理解，这里说不清楚，最好让别人当面给你讲

---

作者: 杨震    时间: 2012-8-25 21:41
楼主都搞了十八分了，求指导如何挣分

---

作者: 黑马-李勇    时间: 2012-8-26 00:51
没做出递归来。求解。晕......
很笨的方法。
        public static void fbnq1(int end)
        {
                int x=1,y=1;   //输出两个1.
                System.out.print(x+",");
                System.out.print(y+",");
                int t=0;             //临时值
                for (int i=2;i<=end;i++)
                {
                        System.out.print(x+y+",");
                        t=0;               //计算x,y的下一个数。
                        t=x;
                        x=y;
                        y=t+x;
                }
        }

---

作者: 黑马_许芸    时间: 2012-8-26 08:45
if (n == 1 || n == 2) {
                         return 1;
这句不就是出口吗？
停止调用自身就出去了呗。

---

作者: 高廷平    时间: 2012-8-26 19:06
要理解递归的执行过程，先得弄懂：栈！数据结构中的知识。建议看看再说。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2