黑马程序员技术交流社区

标题: 请教一个递归问题 [打印本页]
作者: 小小    时间: 2012-6-5 13:41
标题: 请教一个递归问题
  1. public class MethodDemo08 {
  2.         public static void main(String[] args) {
  3.                 int sum = 0;
  4.                 sum = fun(100);
  5.                 System.out.println("计算结果：" + sum);
  6.         }

  8.         public static int fun(int temp) {
  9.                 if (temp == 1) {
  10.                         return 1;
  11.                 } else {
  12.                         return temp + fun(temp - 1);
  13.                 }
  14.         }
  15. }
复制代码
我不太明白，递归是调用自己的方法，但是100+99+...+1的时候，也就是当temp=1的时候，函数就返回了1，根本就不用执行else语句，整个函数的结果应该是1，为什么是5050呢？
作者: 唐辉辉    时间: 2012-6-5 13:44
return 1; 并不是直接返回到主函数里，而是一层一层的往上返回！
作者: 王渠    时间: 2012-6-5 13:50
结果是没有错的吧，可以想一下fun(2)，
fun（2）=2+fun（1），所以，结果是5050也就是完全正确的了
作者: 李天甲    时间: 2012-6-5 13:52
本帖最后由 李天甲 于 2012-6-5 13:57 编辑

楼主被return搞晕了,调试了一下
改写一下可能清楚一些...
  1. public class MethodDemo08 {
  2.     public static void main(String[] args) {
  3.         int sum = 0;
  4.         sum = fun(100);
  5.         System.out.println("计算结果：" + sum);
  6.     }
  7.     public static int fun(int temp) {
  8.         if (temp == 1) {
  9.             return 1;  ////这里return返回的是1
  10.         } else {
  11.             temp=temp + fun(temp - 1); // fun(temp - 1) 返回值就是下面的return的结果,然后加上temp原有的值从新赋给temp
  12.             return temp; //这里返回temp给上一层
  13.         }
  14.     }
  15. }
复制代码
作者: 张少威    时间: 2012-6-5 13:54
其实递归并不难理解，就是进栈和出栈，画个图应该会比较好理解一点：
作者: 黄克帅    时间: 2012-6-5 13:58
本帖最后由 黄克帅 于 2012-6-5 14:01 编辑

程序是这样执行的
100+fun(99+fun(98+fun(97+...fun(1))));
当fun(1)执行完，返回1，
回到fun(2)继续执行fun(2)(即2+fun(1))，就是2+1，返回3，
回到fun(3)继续执行fun(3),即3+fun(2),就是3+3，fun(3)返回6，
回到fun(4)继续执行fun(4), fun(5),fun(6)......fun(100)   最后结果就相当于 100+99+...+1   
作者: 韩健    时间: 2012-6-5 14:00
sum = fun(100);
fun(100) = 100 + fun(99);  fun(99) = 99 + fun(98) 接着递归
fun(3) = 3 + fun(2);   fun(2) = 2 + fun(1);   f(1) = 1;
所以 sum = 100 + 99 +....+ 2 + 1;
并不是一开始就执行fun(1)就返回1结束....而是由fun(100)开始递归.
作者: 金鑫    时间: 2012-6-5 14:01
本帖最后由 金鑫 于 2012-6-5 14:02 编辑

递归是自己调用自己的方法，其实不断的调用，直到不满足条件结束的方式与循环有点类似。

sum = fun(100);在else内当sum=100时，返回的是 return temp + fun(temp - 1);即：renturn 100+fun(100-1)。

因为100-1满足else语句，所以他第二次返回的是return 99+fun(99-1)。

这样不停的循环调用，直到fun(2-1)的时候，因为此时temp-1传递的值是1，所以进到if语句里面去，返回的是1。

这样以来实际的运算结果就是100+99+98+97+96+.....1；结果是5050；
作者: 郭宁    时间: 2012-6-5 14:08
本帖最后由 郭宁 于 2012-6-5 14:09 编辑

来个通俗版的，不敢确定对错哈！：
     递归其实就像放箱子，第一个箱子放了n=100个，再在这个箱子上放 n-1 ，依次往上放，直到这个箱子剩一个了（出口）这其实就是入栈过程。
然后开始往下搬箱子（出栈）但搬箱子有个规则》》把上面箱子的物品放到下面箱子里面（这才算开始真正的计算过程），空箱子就被抛弃了（垃圾）
搬到最后结果不就有了？

总结：递归就是一个入栈出栈的过程
作者: 马东华    时间: 2012-6-5 14:37
本帖最后由 马东华 于 2012-6-5 14:40 编辑


以fun（4）为例
作者: 付信榕    时间: 2012-6-5 15:25
递归的概念前面几楼已有解释了。楼主的疑问其实就是这题递归的一个终止条件，只执行return1，不再去调用自己的方法进行递归了，如果没有这个终止条件就会使一个死循环。所以，每个递归都应该要有结束递归终止条件，否则就是死循环。



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