Short Java FizzBuzz using recursion and parameters

Question

public void fizzbuzz(int count, int max, String fizzer) {
    fizzer += (count % 3 == 0) ? "fizz":"";
    fizzer += (count % 5 == 0) ? "buzz":"";
    fizzer += (count % 3 != 0 && count % 5 != 0) ? count:"";
    if (count != max) {
        fizzer += "\n";
        fizzbuzz(count+1,max,fizzer);
    } else {
        System.out.println(fizzer);
    }
}

fizzbuzz(1,30,"");

The code is performing fizzbuzz over the range count to max. No variables are initialized within the method.

I'd love to get rid of max, and instead take only two arguments for the method (String fizzer and int count), but how can I? I can do it backwards (i.e. working down until reaching the trivial case count == 0 and then stop), but is there a way to go from 1 to n with only one argument?

Answer 1

Recursion is usually not a favoured strategy in Java due to concerns about stack overflow and function call efficiency. However, we can still review FizzBuzz as an exercise in recursive programming.

The first observation I have is that recursive solutions usually start by checking for the base case first. I recommend that you stick to that pattern. As a bonus, checking for count > max will prevent infinite recursion if the function is accidentally called with the count and max parameters reversed.

Another typical feature of recursive solutions is that they avoid mutation and reassignment. When you recurse, previous values of your variables will already be kept on the stack for you, and that is generally sufficient to solve most problems. In your case, you've used +=, whereas you should be able to use just +.

You've used three ternary conditionals. If you reorder them, you can avoid concatenating += "fizz" followed by += "buzz".

Since this is a pure function, it should probably be declared static, so that you don't have to instantiate an object just to call the code.

Finally, note that the resulting string is already terminated by \n, so perhaps you should call System.out.print() rather than .println().

public void fizzbuzz(int count, int max, String accumulator) {
    // Check for the base case
    if (count > max) {
        System.out.print(accumulator);
        return;
    }

    // ... then proceed to the recursive cases.
    //
    // The first case below would be better written as (count % 15 == 0),
    // but I've kept it as (count % 3 == 0 && count % 5 == 0) for easier
    // comparison with your original code.
    String fizzer = (count % 3 == 0 && count % 5 == 0) ? "fizzbuzz\n" :
                    (count % 3 == 0) ? "fizz\n" :
                    (count % 5 == 0) ? "buzz\n" : count + "\n";
    fizzbuzz(count + 1, max, accumulator + fizzer);
}

---

You asked about reducing the number of parameters. The first parameter I would eliminate is not count or max, but the accumulator. You could change it into a return value instead, and it would be more natural. The caller would have to be responsible for printing the result — and I would also consider that an improvement, since it keeps the calculation and the output routines separate.

public static String fizzbuzz(int count, int max) {
    if (count > max) {
        return "";
    }
    String fizzer = (count % 15 == 0) ? "fizzbuzz\n" :
                    (count %  3 == 0) ? "fizz\n" :
                    (count %  5 == 0) ? "buzz\n" :
                                        count + "\n";
    return fizzer + fizzbuzz(count + 1, max);
}

public static void main(String[] args) {
    System.out.print(fizzbuzz(1, 30));
}

---

Once you've done that, you can eliminate one more parameter by making it left-recursive instead of right-recursive.

public static String fizzbuzz(int n) {
    if (n <= 0) {
        return "";
    }
    String fizzer = (n % 15 == 0) ? "fizzbuzz\n" :
                    (n %  3 == 0) ? "fizz\n" :
                    (n %  5 == 0) ? "buzz\n" :
                                    n + "\n";
    return fizzbuzz(n - 1) + fizzer;
}

public static void main(String[] args) {
    System.out.print(fizzbuzz(30));
}

Answer 2

fizzer and max don't change: instead they could both be member data of the class (passed to the class constructor).

Answer 3

A wild suggestion, count the number of \n in your output String and use that to determine when to exit the recursion!

Also, I'll implement the fizzbuzz in one if-else-if block statement instead of three ternary statements, the main reason being that I don't have to append empty Strings. This may be just me though.

Answer 4

The aspect of "an exercise in writing a recursive fizzbzz" has already been addressed in other answers. There are issues with this in Java (stack frames) that make it a less than ideal option for the language.

Another issue that comes up is the String. Since String is an immutable, each time one is modified a new String is instantiated.

From:

public void fizzbuzz(int count, int max, String fizzer) {
    fizzer += (count % 3 == 0) ? "fizz":"";
    fizzer += (count % 5 == 0) ? "buzz":"";
    fizzer += (count % 3 != 0 && count % 5 != 0) ? count:"";
    ...
}

This will instantiate a three new strings, which are then thrown away as a new one is created. Furthermore, this string keeps on growing. With a sufficiently long fizzbuzz (or other recursive call) you will be creating and discarding an inordinate number of ever increasing length Strings.

Instead of using an immutable String (yes, immutability is nice and one of the ideals of functional programming), consider working with a StringBuilder instead:

public void fizzbuzz(int count, int max, StringBuilder fizzer) {
    fizzer.insert('\n');
    fizzer.insert(0, (count % 5 == 0) ? "buzz":"");
    fizzer.insert(0, (count % 3 == 0) ? "fizz":"");
    if (count % 3 != 0 && count % 5 != 0) {
        fizzer.insert(0, count);
        // insert(0, true ? 2 : "") has mixed types (int, String) - doesn't work
    }
    ...
}

---

Note that this is going to suffer from poor performance because of the O(N) .insert call (it has to shift the entire array that backs the StringBuilder). Over the entire range, this becomes O(N²). Looking at the code for insert, though, this isn't going to suffer from an excess of objects (just that painful System.arraycopy).

One may wish to instead use a LinkedList which allows for O(1) insert and put each element in the list, and have the initial invocation then walk the list and print everything out in the proper order.

^{_{As an aside, if you do want to play with recursive FizzBuzz in a Javaish environment, consider a nice Clojure or Scala approach which would play a bit nicer with recursion}}