What do you think of my Recursive FizzBuzz?

Question

I wanted to see if I fully understood recursion so I attempted the FizzBuzz challenge and applied recursion to it.

Did I do it correctly? Is this good code? Is there a more efficient way of doing it? How can I improve?

//---------------------------------------------------------------------------------------
//[RecurFizzBuzz]
//  FizzBuzz using recursion
//---------------------------------------------------------------------------------------
// Author : Jimmy
//---------------------------------------------------------------------------------------

public class RecurFizzBuzz {

 // Specify a range to recurse, starts at int a, ends at int b
 public static void recurse(int a, int b){

  if(a <= b){
   if(a % 3 == 0 && a % 5 == 0){
    System.out.println("FizzBuzz");
   } else if(a % 3 == 0){
    System.out.println("Fizz");
   } else if(a % 5 == 0){
    System.out.println("Buzz"); 
   } else {
    System.out.println(a);
   }
   recurse(++a, b);
  } else {   
   System.exit(0);
  }
 }

 public static void main(String[]args) {
  recurse(1, 100);
 }
}

Answer 1

1. It's worth to mention a disadvantage of recursion: the possibility of stack overflow. Calling recurse(1, 6500) throws a StackOverflowError on my machine.

2. a % 3 == 0 && a % 5 == 0 could be a % 15 == 0. (Deleted, based on @QPaysTaxes's comment.)

3. recurse isn't a descriptive method name. printFizzBuzz would be better.

4. Use longer variable names for the parameters which explain the purpose, for example: lowerBound and upperBound. They're easier to read and maintain.

   Without proper names, we are constantly decoding and reconstructing the information that should be apparent from reading the code alone.

   (From codesparkle's former answer.)

5. System.exit isn't the nicest way to stop the recursion. You could use a simple return or omit the whole else block since the method returns anyway.

Answer 2

Your recursion looks solid to me if you only wish to print the results. However, often recursion is used so that the recursive function actually has a return value. It's more useful that way when you can do whatever you want with the result, instead of only printing it. That printer-method is also difficult to test with unit tests. So try changing the method from returning void to, say, String, and then concatenating the current result with the results-to-come:

public static String recurse(int a, int b) {
    String result;
    if (a <= b) {
        final int mod3 = a % 3;
        if (mod3 == 0 && a % 5 == 0) {
            result = "FizzBuzz";
        } else if (mod3 == 0) {
            result = "Fizz";
        } else if (a % 5 == 0) {
            result = "Buzz";
        } else {
            result = String.valueOf(a);
        }
        return result + "\n" + recurse(++a, b);
    } else {
        return "";
    }
}

You'll notice that I also stored the result of a % 3 and reused it in the second else-if block, because it makes the program run a tiny bit faster when it doesn't need to calculate the same value for the second time. According to my benchmarks, storing the result of a % 5, on the other hand, does not make the program run faster, as it's not needed as often as the result of a % 3.

Answer 3

Well, this is not that good example for recursion.
My suggestion:

public static void printFizzBuzzFromToInclusive(final int start, final int end) {
    if (start <= end) {
        String toPrint = "";
        if (start % 3 == 0)
            toPrint += "Fizz";
        if (start % 5 == 0)
            toPrint += "Buzz";
        System.out.println(toPrint.length() > 0 ? toPrint : start);
        printFizzBuzzFromToInclusive(start + 1, end);
    }
}

public static void main(final String[] args) {
    printFizzBuzzFromToInclusive(1, 100);
}

Most of the changes are documented in the answer from palacsint.
Additions:

• Do not use ++ for an argument. Try to keep your arguments final or unexpected things can happen (e.g. with ++ side effects if you use the variable somewhere after this line of code)
• For readability, I like the String concatenating approach. But this is only taste.
• You do not need a else cause, because the action (print) is always done inside the if case.

For efficiency: There are some ways, but for the typical situation (job interview) you should aim for the solution with best readability (which is not necessarily the recursive way, but well).
If someone asks you about it, always claim that readability is the first major goal (there are many reasons, main reason is the cost of support, which makes easily more than 90% of a project). Than, if you need speed, start profiling it and do the right thing.

For this approach, you could talk about:

• Make it a while loop
• Use StringBuffer
• Use custom output channel
• Use int/byte array and set the corresponding results (0=number 1=fizz 2=buzz 3=fizzbuzz) (no modulo is needed anymore)
• Unroll the loop (then you do not need any modulo any more)

Specific improvements depending on the exact requirements:

• Precalc the solutions up to a specific number
• Use multithreaded (either fork/join with an array or multiple threads with different steps)
• Talk with the customer to get rid of this thing
• Do it in some other language, where you can code for specific cpu architecture features

Answer 4

Recursive solutions are generally short in terms of lines of code. Yours appears to have too many lines at first glance.

My expectation of a recursive method is that it will check for some end condition first otherwise it will call itself with a modification of the input parameter received.

Fibonacci example

 public long fib(int n) {
    if (n <= 1) {
      return n;
    }
    else {
      return fib(n-1) + fib(n-2);
    }
}

Suggestion #1

Having said that, your implementation is 'backwards' because you aren't checking for the end condition first - you are checking if you can keep going, if(a <= b), and your end condition is at the bottom, System.exit(0).

Suggest swapping the order: check for end condition first so you can exit immediately otherwise keep processing.

---

Suggestion #2

Extract all of the code relating to printing into its own method. This will greatly simplify the recursive method and increase its readability.

 private static void evaluate(int a) {
     if (a % 3 == 0 && a % 5 == 0){
         System.out.println(a + " - FizzBuzz");
     } else if(a % 3 == 0) {
         System.out.println(a + " - Fizz");
     } else if(a % 5 == 0) {
         System.out.println(a + " - Buzz");
     }
}

---

Suggestion #3

In the fizzbuzz problem, I am not a fan of a two parameter method - it seems like overkill. You can get away with just passing in one parameter - the number that you are currently processing. This is because one of the numbers (1 or 100, depending where you start from) never changes!

Your method could be simplified to this:

 public static int calculate(int value)

Feel free to keep the second parameter in the method signature if you think the bounds of the problem will change.

---

Putting it all together

Starting from 1 and going up to 100:

public static int calculate(int value) {
    if (value > 100) {
        return 0;
    } else {
        evaluate(value);
        return calculate(++value);
    }
}

Starting from 100 and going down to 1:

public static int calculate(int value) {
        if (value== 0) {
            return 0;
        } else {
            evaluate(value);
            return calculate(--value);
        }
    }