0

I have the below recursive function to compute factorial of a number. The program works fine except when I remove the if condition. Can someone explain why?

This is the code that works fine --

public static long factUsingRecursion(int number) {
    if (number == 1) {
        return 1;
    } else {
        return number * factUsingRecursion(number - 1);
    }
}

Without the if condition (Code that throws the error), 

public static long factUsingRecursion(int number) {
    return number * factUsingRecursion(number - 1);
}

I get the stack overflow error.

Exception in thread "main" java.lang.StackOverflowError at birst.FactorialUsingRecursion.factUsingRecursion(FactorialUsingRecursion.java:10)

Request experts to please advise me why this is the case?

4

7 回答 7

7

在递归中，必须始终存在停止递归的基本情况。没有if，你就没有基本情况，也没有什么能阻止它。最终太多的方法调用在堆栈上并产生StackOverflowError结果。

于 2013-06-20T21:06:41.210 回答
2

此行导致number变量减少 1

return number * factUsingRecursion(number - 1);

它将处理number除 1 以外的所有值

所以这行代码是一个中断条件

if (number == 1) {
        return 1;

}

它会阻止您避免 stackoverflow 异常

于 2013-06-20T21:07:06.210 回答
2

递归需要一个基本案例。没有它，它将继续一遍又一遍地调用该函数，并且永远不会停止。if 语句是基本情况，它终止递归。这就是为什么如果你删除它，你会得到一个StackOverflowError.

于 2013-06-20T21:08:07.167 回答
2

想象一下当你打电话时会发生什么：

factUsingRecursion(3);

如果：

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1

没有如果：

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1*factUsingRecursion(0)
3*2*1*0*factUsingRecursion(-1)
3*2*1*0*-1*factUsingRecursion(-2)
3*2*1*0*-1*-2*factUsingRecursion(-3)
...
And so on... It will not stop until you encounter the StackOverflow error
于 2013-06-20T21:11:11.757 回答
1

它失去了使递归函数递归的原因之一，因为它没有退出条件。

所有递归解决方案都必须满足三个规则或属性： 递归解决方案必须包含基本案例。递归解决方案必须包含递归案例。递归解决方案必须朝着基本情况取得进展。

来自：使用 Python 的数据结构和算法

于 2013-06-20T21:06:44.753 回答
1

当您删除 if 条件时，该程序将不再工作，因为您将只剩下return number * factUsingRecursion(number - 1);并且factUsingRecursion(number - 1)here 将具有相同的 return 调用return number * factUsingRecursion(number - 1);。你的函数不断地调用自己，永远无法评估任何东西。通过设置条件，您的函数能够在递归链中的某个点评估为确定值，并且第一次调用可以评估。

于 2013-06-20T21:08:52.560 回答
0

对于每个整数 i，您都使用 i -1 调用该函数。Integersa 是无限的，因此您将永远不会停止调用该函数。例如：-1000 会调用 -1001 并且只要 JVM 的堆栈中有一些空间，它就会继续运行。

于 2013-06-21T10:21:34.803 回答