如何管理递归函数？

Question

我需要编写一个获取4个参数的递归函数。

第一个是数组。第二个 - 左指数，第三个是右指数和“K”指数。 “K”索引是一个数组中的单元格，lrft索引指向开始，右侧指向结尾。

一个数组可能包含诸如零和一的洋地黄。该方法返回包含单元格k的序列的最大长度。

在这里，我需要得到的结果的例子：

public static void main(String[] args) { 
    int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
    System.out.println(floodOnes(A,0, A.length-1, 9)); // 5 output 
    System.out.println(floodOnes(A,0, A.length-1, 3)); // 0 output 
    System.out.println(floodOnes(A,0, A.length-1, 0)); // 3 output 
    System.out.println(floodOnes(A,0, A.length-1, 14)); // 2 output 
} 

public static int floodOnes(int [] A,int left, int right, int k){ 
    //some logic 
} 

这是我实现：

public class Program { 
    public static void main(String[] args) { 
     int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
     System.out.println(floodOnes(A,0,A.length-1, 9)); 
    } 

    public static int floodOnes(int [] A,int left, int right, int k){   
     if (left != k) left+=1; 
     if (right != k) right-=1; 

     if (left == k && right == k) return A[k]; //condition when the recursive call stops 

     int res = floodOnes(A, left, right, k); 

     if (A[left] == 1 && A[right] == 1) 
      return res = A[left] + A[right]; //count ones  

     else return res; 
    } 
} 

但我的解决方案不能正常工作。

在这行：

if (A[left] == 1 && A[right] == 1) 
     return res = A[left] + A[right]; //count ones 

如果条件之一isn`t执行一次，下面的收益不应附加产品造成的变量。

我不知道该怎么做。

Answer 1

既然您正在寻找 - the maximum length of a sequence of ones that contain the cell k。一个简单而简洁的代码可以实现如下。

public static void main(String[] args) { 
    int[] A = {1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1}; 
    System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
    System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 0 
    System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
    System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 
} 

public static int checkLeft(int[] A, int k) { 
    return (k < 0 || A[k] != 1) ? 0 : 1 + checkLeft(A, k - 1); 
} 

public static int checkRight(int[] A, int k) { 
    return (k > (A.length - 1) || A[k] != 1) ? 0 : 1 + checkRight(A, k + 1); 
} 

public static int floodOnes(int[] A, int left, int right, int k) { 
    return (A[k] != 1) ? 0 : checkLeft(A, k - 1) + 1 + checkRight(A, k + 1); 
} 

它输出所需的结果。

5 
0 
3 
2 

Answer 2

您可以将此问题分解为2个函数。 第一个将在左侧计算元素，后一个在右侧。两者都使用递归。

public static int floodOnes(int[] A, int left, int right, int k) { 
    return checkLeft(A, left, k-1, A[k]) + 1 + checkRight(A, right, k+1, A[k]); 
} 

public static int checkLeft(int[] A, int leftBoundary, int k, int number) { 
    if (k < 0 || A[k] != number || k < leftBoundary) 
     return 0; 
    return 1 + checkLeft(A, leftBoundary, k-1, number); 
} 

public static int checkRight(int[] A, int rightBoundary, int k, int number) { 
    if(k >= A.length || A[k] != number || k > rightBoundary) 
     return 0; 
    return 1 + checkRight(A, rightBoundary, k+1, number); 
} 

我认为：
是0 <= left <= k <= right < A.length;
不像你的例子，孤立数应该算作1（长度为1的序列）。如果您希望将其计为0，请在floodOnes方法中添加if(A[k] != 1) return 0;或类似的条件。

因此：

System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 1 
System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 

除了left和right参数可用于一些输入例外 （例如k > A.length）。

Answer 3

我证明我的评论错了。这是一个递归方法，其中提到的4个参数确实可以解决问题。

public static int floodOnes(int[] a, int left, int right, int k) { 
    if (0 <= left && left <= k && k <= right && right < a.length) { 
     // is there a 0 between left (inclusive) and k (exclusive)? 
     int i = left; 
     while (i < k && a[i] == 1) { 
      i++; 
     } 
     if (i < k) { 
      assert a[i] == 0; 
      return floodOnes(a, i + 1, right, k); 
     } 
     // is there a 0 between k (exclusive) and right (inclusive)? 
     i = right; 
     while (i > k && a[i] == 1) { 
      i--; 
     } 
     if (i > k) { 
      assert a[i] == 0; 
      return floodOnes(a, left, i - 1, k); 
     } 
     // no zero found, a[k] not checked, though 
     if (a[k] == 0) { 
      return 0; 
     } else { 
      return right - left + 1; 
     } 
    } else { 
     throw new IllegalArgumentException("Expected " + left + " <= " + k + " <= " + right + " < " + a.length); 
    } 
} 

通过这种方法，在你的问题第一main方法打印预期：

5 
0 
3 
2 

我真的没有看到在解决这样的问题点，所以我从很远确定这是预期的。我更喜欢非递归解决方案，或者它只是需要以某种方式递归，然后解决方案Grzegorz Górkiewicz’ answer。