黑马程序员技术交流社区

标题: 递归的一个疑问 [打印本页]

---

作者: 涂金哲    时间: 2012-7-4 17:35
标题: 递归的一个疑问


class Test
{
    int result;
    int fact(int n){
        int result;
        if(n==1)
            {
                return 1;
            }
            else
                {
                    result=fact(n-1)*n;
                    System.out.println(fact(n-1));//我想打印fact（n-1）是什么？
                    return result;
                }
        }

}
class Fun
{
    public static void main(String[] args)
    {
        Test t=new Test();
        System.out.println(t.fact(5));
    }
}
当变元5传入时，首先是4调用fact（）方法，然后使3调用fact（）方法……直到1去调用。我想知道fact(1）、fact（2）……是什么？因为它们要逐级返回给调用的上一级，于是我就想打印fact（n-1），结果显示的是很多不能理解的数字，或者说用什么方法能知道fact（n-1）？向大家请教

---

作者: 蒋映辉    时间: 2012-7-4 17:47
什么叫递归？你可以去研究一下汉诺塔的问题 我觉得那是理解递归最好的题目   递归，说白了也就是一个函数反复调用自身，它只对它的上一位负责，至于上一位怎么做，又是他的事情了....这样一直返回到头，又把值推过来 才得到结果。
t.fact(5)  我们不知道fact(5) 是多少  我们知道当fact(1)=1;如果n>1 则等于fact(n-1)*n  给你推理一下思路
fact(5)=fact(4)*5=fact(3)*4*5=fact(2)*3*4*5=fact(1)*2*3*4*5=120我这个推理是简化以后的 真实的推理是正推过去  推到头又把值返回推过来
System.out.println(fact(n-1));//我想打印fact（n-1）是什么？  实际上就是2  2*3  2*3*4   2*3*4*5

---

作者: 涂金哲    时间: 2012-7-5 09:36

蒋映辉 发表于 2012-7-4 17:47
什么叫递归？你可以去研究一下汉诺塔的问题 我觉得那是理解递归最好的题目   递归，说白了也就是一个函数反 ...

递归的过程我懂、我想知道它的算法的实现过程……查了一些资料，说返回的那些数字是调用的级别和中间结果

---

作者: 杨朔    时间: 2012-7-5 11:43
这个问题比较复杂，关于这个递归的执行顺序，首先，依次把n的fact（n）变小，依次变为
fact（4）*5、fact（3）*4、fact（2）*3、fact（1）*2，然后return 1，此时开始执行这句System.out.println(fact(n-1));
先返回的就是最后一个fact（1）*2，再依次往后面返回，但是因为每一次都要执行fact(n-1)这个，所以当执行
fact（2）*3这个的时候又会向后执行一遍，依次类推，return要执行8次，fact（1）*2要执行4次，
fact（2）*3要执行2次，fact（3）*4要执行1次。
最后再打印result。

---

作者: 黑马-李勇    时间: 2012-7-5 13:28
class Test
{
    int result;
    int fact(int n){
        int result;
        if(n==1)
            {
                return 1;
            }
            else
                {
                    
                    result=fact(n-1)*n;
                    //System.out.println("fac(n-1)="+fact(n-1));//我想打印fact（n-1）是什么？
                    System.out.println("当n="+n+"时 fact("+n+")="+"fact("+(n-1)+")*"+n+"  中间结果result=fact("+n+")="+result);
                        return result;
                }
        }

}
class demo
{
    public static void main(String[] args)
    {
        Test t=new Test();
        System.out.println("main::"+t.fact(5));
    }
}
打印结果：
当n=2时 fact(2)=fact(1)*2  中间结果result=fact(2)=2
当n=3时 fact(3)=fact(2)*3  中间结果result=fact(3)=6
当n=4时 fact(4)=fact(3)*4  中间结果result=fact(4)=24
当n=5时 fact(5)=fact(4)*5  中间结果result=fact(5)=120
main::120
----------------输出语句有点乱{:soso_e113:}

---

作者: 涂金哲    时间: 2012-7-5 13:40

杨朔 发表于 2012-7-5 11:43
这个问题比较复杂，关于这个递归的执行顺序，首先，依次把n的fact（n）变小，依次变为
fact（4）*5、fact（ ...

谢谢……从结果看是先打印fact（1）……逐级返回到fact(5).它的底层不知道是怎么实现的 但是可以看出每次调用时都从头开始了 如：传入4，先fact（1）执行，返回上一级；fact（2）从fact（1）执行，返回上一级；fact（3）从fact（1）执行，返回……

---

作者: 涂金哲    时间: 2012-7-5 13:48

黑马-李勇 发表于 2012-7-5 13:28
class Test
{
    int result;

不会吧 你那输出不是阶乘的最终结果嘛  我觉得 fact（n-1）……fact（1）为fact（n）的中间结果。

---

作者: 黑马-李勇    时间: 2012-7-5 14:00
class Test
{
    int result;
    int fact(int n){
        int result;
        if(n==1)
            {
                return 1;
            }
            else
                {
                    System.out.println("调用"+(n-1));
                    result=fact(n-1)*n;
                    //System.out.println("fac(n-1)="+fact(n-1));//我想打印fact（n-1）是什么？
                    System.out.println(" 返回"+n+" 当n="+n+"时 fact("+n+")="+"fact("+(n-1)+")*"+n+"  中间结果result=fact("+n+")="+result);
          return result;
                }
        }
}
class demo
{
    public static void main(String[] args)
    {
        Test t=new Test();
        System.out.println("main::"+t.fact(5));
    }
}

未命名.JPG (34.32 KB, 下载次数: 49)

下载附件

2012-7-5 13:59 上传

---

作者: 黑马-李勇    时间: 2012-7-5 14:01
应该这样理解

---

作者: 杨朔    时间: 2012-7-5 14:41

涂金哲 发表于 2012-7-5 13:40
谢谢……从结果看是先打印fact（1）……逐级返回到fact(5).它的底层不知道是怎么实现的 但是可以看出每次 ...

我是怎么理解的

---

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

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