阶乘问题在 c++ 中给出错误的输出

Question

试图为我的课堂作业编写阶乘问题，但得到错误的输出。不明白我做错了什么。这是我的代码。

int fact(int number) {
if(number == 0) {
return 1;
}
return  fact_i(number, 1);
}
int fact_i(int curNumber, int sum) {
if(curNumber == 1) {
return sum;
} else {
return fact_i(curNumber - 1, sum);
}
}

Answer 1

1. 您永远不会将sum乘以数字，因此它不能超过一个。递归应为：

   return fact_i(curNumber - 1, curNumber * sum);
   

2. 请注意，在这种情况下，针对尾部调用优化是没有意义的。虽然C++编译器通常可以做到这一点(如果有的话，C++哪个编译器会做尾递归优化？(，但你不能依赖它，因为它没有指定，而且在你遇到任何堆栈限制之前，你会溢出int方式。

Answer 2

问题

错误出在行中

return fact_i(curNumber - 1, sum);

它需要：

return curNumber*fact_i(curNumber - 1, sum);

没有它，结果永远不会累积。你只是继续1递归调用链上传递。

进一步清理

您正在使用两个终止条件 - 一个是fact，另一个是fact_i。可以只使用一个终止条件来简化代码。

int fact_i(int curNumber, int sum) {
if(curNumber == 1) {
return sum;
}
// No need for an else here.
return fact_i(curNumber - 1, (curNumber-1)*sum);
}
int fact(int number) {
return  fact_i(number, number);
}

Answer 3

执行尾递归阶乘的正确方法是：

int fact(int number) {
if(number == 0) {
return 1;
}
return  fact_i(number, 1);
}
int fact_i(int curNumber, int sum) {
if(curNumber == 1) {
return sum;
} else {
return fact_i(curNumber - 1, sum*curNumber);
}
}

您错过了行中与sum乘curNumberreturn fact_i(curNumber - 1, sum);