java - 递归 - 在二进制表示中查找 1 的连续计数

Question

我开始学习递归并尝试解决以下问题: 问题陈述: 需要查找二进制数中连续的个数:

Example:

The binary representation of 13 is 1011 , so the maximum number of consecutive 1's is 2.

我在 while 循环的帮助下实现了上述目标。然而，我试图通过递归实现解决方案但面临问题:

使用 While 循环:

int counter = 0, max =0, n=13;
    while (n > 0) {
        int rem = n%2;
        if (rem==1) counter++; 
        else counter=0;
        max = Math.max(counter, max);
        n/=2;
    }
    System.out.println(max);

Result : 2

递归:

public static int returnCount(int n,int count,int max){

        if (n > 0){
            int temp=n%2;
            if(temp==1)
                count++;
            else
                count=0;

            n/=2;
            max=Math.max(count,max);
            returnCount(n,count,max);           
        }
        return max;
    }

结果:1​​

请帮我纠正上面代码段中的错误。

Answer 1

当您对 returnCount 进行递归调用时，您永远不会使用它返回的值。在您的解决方案中，如果 n 为奇数，则 returnCount 始终返回 1，因为从未使用对 returnCount 的递归调用的返回值。

public static int returnCount(int n, int count, int max) {
    if (n > 0){
        if(n % 2 == 1)
            count++;
        else
            count = 0;
        n /= 2;
        max = Math.max(count, max);
        max = returnCount(n, count, max);           
    }
    return max;
}

为了证明我的观点，我将稍微跟踪一下代码。如果我们对您的代码运行以下调用:

int answer = returnCount(13, 0, 0);

我们最终调用了以下方法:

1. returnCount(13, 0, 0)
2. returnCount(6, 1, 1)
3. returnCount(3, 0, 1)
4. returnCount(1, 1, 1)
5. returnCount(0, 2, 2)

在第四次调用的迭代过程中，count 递增到 2，max 被赋值为 2，因为 count> 最大。到第五次调用时，找到了答案，max 仍然是 2。

但是，当从第一次调用返回时，局部变量 max 仍被赋值 1。我们问题的正确答案丢失了，因为它从未从您的第四次和第五次调用中返回解决方案。