1

我试图理解以下问题：

public class Main {
    public static int fact(int n){
        if (n == 0){
            return 1;
        }else{
            return n * fact(n - 1);
        }
    }
    public static void main(String[] args){
      System.out.print(fact(5));
    }
}

当编译器通过时，return n * fact(n - 1);它实际上是乘以n还是仅在达到基本情况后才这样做，然后乘以存储在堆栈中的所有值？

注意我对这种递归编码方式仍然很陌生。

4

5 回答 5

1

查看乘法执行顺序的好方法，替换n * fact(...)为mult(n, fact(...))wheremult是您编写的一种方法，该方法接受两个数字并返回它们的乘积。然后您可以在 中添加一些输出打印mult，并查看调用的顺序。

public class FactorialExample {
    // The new mult method.
    private static int mult( final int x, final int y ) {
        System.out.println( "Multiplying "+x+" and "+y+"." );
        return x * y;
    }

    public static int fact(int n){
        if (n == 0){
            return 1;
        }else{
            return mult(n, fact(n - 1)); // using the new mult method
        }
    }

    public static void main(String[] args){
      System.out.print(fact(5));
    }
}

这会产生以下输出：

Multiplying 1 and 1.
Multiplying 2 and 1.
Multiplying 3 and 2.
Multiplying 4 and 6.
Multiplying 5 and 24.
120

回想一下，左加数是 对应的n，并且第一次调用fact具有最大值。因此，递归调用fact(4)必须首先完成（产生24），然后5乘以24。

于 2013-10-25T01:37:10.197 回答
0

（注意：编译器不是评估fact的程序；程序本身就是这样做的）。

当程序遇到语句

n * fact(n - 1)

它将通过调用和作为参数传递fact(n - 1)来隔离计算。一旦该函数完成运行并返回，它将具有一个可以乘以 的值。这样做的最终效果是，直到达到基本情况之后才会执行乘法运算，此时存储在堆栈中的值将全部相乘。您可以通过在该行放置一个断点来看到这一点factn - 1nn

return n * fact(n - 1);

并观察程序展开递归以计算总价值。

希望这可以帮助！

于 2013-10-25T01:22:54.317 回答
0 
1. java tries to output unknown value, so java execute fact with N = 5
  2. tries to multiple 5 by value, which is unknown, it executes fact with N=5-1
    3. tries to multiple 4 by value ..... N=3
      4. tries to multiple 3 by value ..... N=2
        5. tries to multiple 2 by value ..... N=1
          6. tries to multiple 1 by value ..... N=0
            7. returns 1 and go back to 6th item
          8. 1*1 = 1 and go back to 5th item
        9. 2*1 = 2 and go back to 4th item
      10. 3*2 = 6 and go back to 3rd item
    11. 4*6 = 24 and go back to 2nd item
  12. 5*24 = 120 and return to 1st item
13. display 120
于 2013-10-25T01:22:57.113 回答
0

它会成倍增加n并且fact(n - 1)一旦fact(n - 1)被评估（直到你达到基本情况。

递归fact()调用被链接在一起，直到最后一个有东西要返回。

于 2013-10-25T01:23:09.043 回答
0

这是简单的递归。与任何递归一样，它首先深入到基本情况（使用堆栈），然后进行乘法（在堆栈展开过程中）

那么，在你的例子中会发生什么，即事实（5）

fact(5) --> 5 * fact(4) // Here another recursive call is made to calculate fact(4)
fact(4) --> 4 * fact(3)//Here another recursive call is made to calculate fact(3)
.
.
.
fact(1) --> 1 * fact(0)// fact(0) is 1 as per your code

从这一点开始，堆栈展开，fact(n)现在每个都由其简化版本表示。最后 fact(5) --> 5 * fact(4)转换为fact(5) --> 5 * 4 * 3 *2 *1

于 2013-10-25T01:26:50.763 回答