java - 零阶乘递归返回 1

Question

我怎样才能让这个递归方法在不测试基本情况的情况下返回1调用0!，即不执行if-else0 和 1。

public static long f( number ){
        if ( number <= 1 ){ // test for base case
                return 1; // base cases: 0! = 1 and 1! = 1
            } 
        else{ return number * f( number - 1 ); }
   }

我不想检查基本情况。这可能吗？

Answer 1

每个递归函数都需要一个必须明确检查的终止条件。如果没有，它将永远运行。所以不，不可能省略基本情况检查

Answer 2

我不想检查基本情况。这可能吗？

不，这是不可能的。您必须测试基本情况，否则算法将不会终止。

Answer 3

尽管您需要一个基本情况，但您只需要检查大小写0（并且为了完整性，也小于 0），否则您只会在无限循环中运行（或直到您遇到堆栈溢出）。您可以缩短代码：

public static long f(int n){
    if (n<0) throw new InvalidParameterException();
    return n == 0 ? 1 : n * f(n-1);
}

Answer 4

好吧，你所说的基本情况是停止递归的条件......你想如何在没有测试的情况下停止递归？

另一方面，迭代版本应该更快。

Answer 5

您总是需要对递归进行基本情况检查以使其有限。顺便说一句，0 的基本情况在阶乘定义中。

Answer 6

使用 if-else or? :是最好的解决方案。即其他任何事情都可能更糟。

public static long f(int n){
  try {
    return 0 / n + n * f(n-1);
  } catch(ArithmeticException ae) {
    return 1;
  }
}

Answer 7

正如其他人所说，您需要一个基本案例，但您不必检查它。以下导致非常糟糕的代码，所以不要在家里尝试这个。这只是一个概念证明。

定义一个函数数组（索引 0 到 21）。每个函数都有一个参数n。索引 0 处的函数对任何返回 1 n，所有其他返回n乘以索引处函数的返回值n-1。从调用 index 处的函数开始n。没有 if-else，没有检查任何东西。

数组大小为 21 就足够了，因为在21!给定的返回类型long（64 位）处溢出并且结果无论如何都是未定义的。如果要避免 OutOfBound 异常，可以添加一个包装器，该包装器使用min (n, 21).