理解递归阶乘中的Java行为

Question

我创建了两个递归方法来计算阶乘,如下所示:

private int fact1(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * fact1(--n);

}

private int fact2(int n) {
    if (n == 0 || n == 1)
        return 1;
    return fact2(--n) * n;
}

当我打电话给fact1(4)它返回24.当我调用fact2(4)它返回时6(编辑:没有返回18但是6).我知道第二种方法是制作3*2*1,但我不明白为什么不是4*3*2*1.

如果我将返回更改为,则会发生相同的情况

//fact3(4) returns 60.
return (n + 1) * fact3(--n); // wrong
//fact4(4) returns 24
return fact4(--n) * (n + 1); // works

为什么该方法表现出这种行为？

问题是关于不同的行为.我知道这n * fact(n-1)是解决问题的更好方法.

有人能帮我理解这个表达式的评价吗？谢谢!

Answer 1

这一切都归结为这些表达式之间的差异:

return n * f(--n);

return f(--n) * n;

何时n = 4,这些表达式的评估方式如下:

return 4 * f(3);

return f(3) * 3;

由于--n评估了时刻,因此值n减1.这是前缀--运算符的工作方式.

手动递归计算整个表达式可能会有所帮助.第一个:

// first
return 4 * f(3);
return 4 * 3 * f(2);
return 4 * 3 * 2 * f(1);
return 4 * 3 * 2 * 1;

// second
return f(3) * 3;
return f(2) * 2 * 3;
return f(1) * 1 * 2 * 3;
return 1 * 1 * 2 * 3;

在相关的说明中,猜猜如何评估:

return f(n--) * n;

这将是:

return f(4) * 3;

因为这里使用了后缀--运算符:在评估nin 后将应用-1减量f(...).