在递归问题中无法 return 基本案例值

Question

编辑：谢谢你的回答，我明白了！

我刚开始学习数据结构，我似乎无法弄清楚为什么基本情况不起作用。在这种方法中，我们应该拆分我们得到的数组并搜索键，如果它比你拆分的地方 bigger/smaller 。找到下面的方法（我去掉了大部分 sys.out.println 因为堆栈溢出说我的代码太多了）：-

public static int nSearch (int n, int a[], int fromIndex, int toIndex, int key){

      //base case
      if ((toIndex - fromIndex) <= n) 
      { // if there is only one element per split or less

          for (int i = fromIndex; i < toIndex; i++) {
        
              if (a[i] == key) {
                  System.out.println("If a[i] == key runs.");
                  return i;
              }
          }
          return -1;
      }
      
      int splitIndex = a.length/n; //2

      if (key >= a[splitIndex]) { // if key is bigger/equal to a[splitIndex], meaning the range is 2-3
          
          nSearch (n, a, splitIndex, a.length, key);
          
      }
      else {

          //else the range is 0-1
          nSearch (n, a, 0, splitIndex, key);
      }

      return 0;
  }

这是我发送测试用例时控制台 returns 的内容：

My Search Tester 2 is Running Now.
Array Length: - 4
Starting nSearch: - n : 2 fromIndex : 0 toIndex : 4
false
Case 1: n = 2 SplitIndex Value = 2 aLength = 4 Key value = 4
Starting nSearch: - n : 2 fromIndex : 2 toIndex : 4
true
Base Case Running
For loop Running
fromIndex : 2 toIndex : 4
i : 2 a[i] : 3 Key : 4
For loop Running
fromIndex : 2 toIndex : 4
i : 3 a[i] : 4 Key : 4
If a[i] == key runs.
Target 4 is at Index := 0

可以看到，输出显示控制进入了if (a[i] == key)块，但是我不明白为什么return i不起作用。请告诉我我做错了什么。

我不能 post 测试代码，以免拒绝我的 post 主要是代码，但这是我正在使用的测试用例：

int arr = {1,2,3,4}
nSearch(2, arr, 0, arr.length, 4);

nSearch 方法应该是二进制搜索的变体，如果有帮助的话。

Answer 1

I don't understand why return i doesn't work

没有理由认为 return 语句没有像宣传的那样工作，但在大多数情况下，程序会忽略生成的 return 值。

但请注意方法末尾的 return 0。你认为在什么情况下执行是合适的？答案：none。我怀疑您添加它是为了清除编译器关于控制到达 non-void 方法末尾的反对意见，但如果是这样，那么您应该更深入地研究：为什么控制首先到达那个点？

考虑紧接在前的位：

      if (key >= a[splitIndex]) { // if key is bigger/equal to a[splitIndex], meaning the range is 2-3
          
          nSearch (n, a, splitIndex, a.length, key);
          
      }
      else {

          //else the range is 0-1
          nSearch (n, a, 0, splitIndex, key);
      }

在每个分支中递归调用 nSearch()，但是当递归调用 return 时会发生什么？没什么特别的。控制只是从那里继续，直接到那个错误的 return 0，它产生测试器报告的 0 return 值。递归调用 returned 的任何值都将被忽略。

您方法最后几行的这种变体应该更适合您：

  if (key >= a[splitIndex]) {          
      return nSearch(n, a, splitIndex, a.length, key);
  } else {
      return nSearch(n, a, 0, splitIndex, key);
  }

  // return 0;

Answer 2

你应该在从内部递归得到结果后终止递归。此外，在此 nSearch (n, a, splitIndex, a.length, key); 中，您正在检查直到 a.length，而不管此方法调用中的实际 toIndex 是什么（fromIndex 相同）。所以以下更改应该会给你正确的答案。

if (key >= a[splitIndex]) {          
    return nSearch(n, a, splitIndex, toIndex, key);
} 
else {
    return nSearch(n, a, fromIndex, splitIndex, key);
}

在递归问题中无法 return 基本案例值

Unable to return base case value in Recursion problem

java

recursion

if-statement

return-value

binary-search