java - 这个递归阶乘函数中的乘法何时完成？

Question

我试图理解以下问题:

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或者它只在到达基本情况后才执行此操作，然后将堆栈中存储的所有值相乘？

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

Answer 1

查看乘法执行顺序的好方法是将 n *fact(...) 替换为 mult(n,fact(...))，其中 mult 是您编写的方法，它接受两个数字并返回它们的乘积。然后，您可以在 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 相乘。