如何在Java中同时递归高效地执行fizzBuzz

Question

PS:这是一个递归通常是愚蠢的问题。

请注意，这不是家庭作业，我知道做递归非常愚蠢，但是为了提高我的递归技巧，我完成了以下问题：

CodingBat code practice
Java > Array-2 > fizzBuzz 
prev  |  next  |  chance

这是著名的FizzBuzz问题的稍微困难的版本，有时作为面试的第一个问题。(另见: FizzBuzz代码。)

考虑从start开始到但不包括end的一系列数字。例如，start=1和end=5给出了系列1, 2, 3, 4。返回一个新的String[]数组，其中包含这些数字的字符串形式，除了3的倍数之外，使用"Fizz“代替数字，对于5的倍数使用"Buzz"，对于3和5的倍数使用"FizzBuzz”。

在Java中，String.valueOf(xxx)将生成int或其他类型的字符串形式。这个版本比通常的版本要复杂一些，因为您必须分配数组并将其索引到数组中，而不仅仅是打印，而且我们改变了开始/结束，而不是总是只执行1..100。

fizzBuzz(1, 6) → {"1", "2", "Fizz", "4", "Buzz"}
fizzBuzz(1, 8) → {"1", "2", "Fizz", "4", "Buzz", "Fizz", "7"}
fizzBuzz(1, 11) → {"1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz"}

还有我的长期递归解决方案代码：

public String[] fizzBuzz(int start, int end) {
    return recurFizzBuzz(new String[end - start], 0, start, end);
}

public String[] recurFizzBuzz(String[] result, int index, int start, int end){
    if(index == result.length - 1 
            && start == end - 1 
            && start % 15 == 0){
        //mod 15, MOD 3 AND MOD 5 
        result[result.length - 1] = "FizzBuzz";
        return result;
    }
    else if(index == result.length - 1 
            && start == end - 1 
            && start % 3 == 0){
        result[result.length - 1] = "Fizz";
        return result;
    }
    else if(index == result.length - 1 
            && start == end - 1 
            && start % 5 == 0){
        result[result.length - 1] = "Buzz";
        return result;
    }
    else if(index == result.length - 1 
            && start == end - 1 
            && start % 3 != 0 
            && start % 5 != 0){
        result[result.length - 1] = "" + start;
        return result;
    }
    if(index < result.length - 1 
            && start < end - 1 
            && start % 15 == 0){
        result[index] = "FizzBuzz";
    }
    else if(index < result.length - 1 
            && start < end - 1 
            && start % 3 == 0){
        result[index] = "Fizz";
    }
    else if(index < result.length - 1 
            && start < end - 1 
            && start % 5 == 0){
        result[index] = "Buzz";
    }
    else if(index < result.length - 1 
            && start < end - 1 
            && start % 3 != 0 
            && start % 5 != 0){
        result[index] = Integer.toString(start);
    }
    return recurFizzBuzz(result, index + 1, start + 1, end);
}

上面的代码通过了所有的测试，但我想不出如何缩短代码。另外，我还必须返回一个String[]数组，因为这是bat编码所需要的，为了返回一个String[]数组，我会如实地打印，但是编写bat的代码除了静态或异常之外。

Answer 1

我建议让递归函数private static，并在顶部添加终止条件，然后在当前index (通过测试index的模糊性)之前在returning之前初始化index

private static String[] recurFizzBuzz(String[] result, int index,
        int start, int end) {
    if (index > result.length) {
        return result;
    }
    if (index % 15 == 0) {
        result[index - 1] = "FizzBuzz";
    } else if (index % 3 == 0) {
        result[index - 1] = "Fizz";
    } else if (index % 5 == 0) {
        result[index - 1] = "Buzz";
    } else {
        result[index - 1] = Integer.toString(index);
    }
    return recurFizzBuzz(result, index + 1, start, end);
}

初始索引是start，类似于

public static String[] fizzBuzz(int start, int end) {
    return recurFizzBuzz(new String[1 + end - start], start, start, end);
}

，它允许类似于main的

public static void main(String[] args) {
    int start = 1;
    int end = 30;
    System.out.println(Arrays.toString(fizzBuzz(start, end)));
}

然后您可以看到输出是(为屏幕格式化的)

[1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 1
    4, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, 
    Buzz, 26, Fizz, 28, 29, FizzBuzz]

Answer 2

关于改变算法和数据结构以及助手方法，可能会有很长的路要走。

public Deque<String> fizzBuzz(int start, int end) {
    Deque<String> stack = new ArrayDeque<String>();
    recurFizzBuzz(stack, start, end);
    return stack;
}

public void recurFizzBuzz(Deque<String> result, int start, int end){
    result.push(determineEntry(end));
    if(start == end) {
         return;
    }
    recurFizzBuzz(result, start, end - 1);
}

public String determineEntry(int value) {
    if (value % 15 == 0) {
        return "FizzBuzz";
    }
    if (value % 5 == 0) {
        return "Buzz";
    }
    if (value % 3 == 0) {
        return "Fizz";
    }
    return Integer.toString(value);
}

Answer 3

以下是我缩短的代码的版本：

public void fizzBuzz(int[] array, String[] output, int start, int end, int i)
{
    if(array[i] % 3 == 0 && array[i] % 5 == 0)
    {
        output[i] = "FizzBuzz";
    }
    else if(array[i] % 3 == 0)
    {
        output[i] = "Fizz";
    }
    else if (array[i] % 5 == 0)
    {
        output[i] = "Buzz";
    }
    else
    {
        output[i] = array[i];
    }
    i++;
    if(i >= end)
    {
        // return array for numbers and output
        return output;
    }
    else fizzBuzz(array, output, end, i);
}

public void printFizzBuzz()
{
    final int TOTAL = 50;
    String[] fizzBuzz = new String[TOTAL];
    int[] nums = new int[TOTAL];

    for (int i = 0; i < TOTAL; i++)
        nums[i] = i;

    fizzBuzz = fizzBuzz(nums, "", TOTAL - 1, 0);

    for (int i = 0; i < TOTAL; i++)
        System.out.println(fizzBuzz[i]);
}