# What do you think of my Recursive FizzBuzz?

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);
}
}

-

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.

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.

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.

-
Thank you for those very valid points! –  user1048606 Nov 19 '12 at 23:49

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.

-
Thanks I'll keep that in mind! –  user1048606 Nov 19 '12 at 23:51
@user1048606 No problem! Actually I suddenly thought of something else besides just reusing the a % 3 result, namely that recursive functions often have return values. I have revised my answer, so please take another look at it! –  ZeroOne Nov 19 '12 at 23:55
+1, nice idea. You could store the result of the comparison too (final boolean mod3 = ((a % 3) == 0)). –  palacsint Nov 20 '12 at 0:00
I'm not sure why you want to store the result of "a % 3", but please don't do it for performance reasons. The compiler (JIT) is perfectly capable of doing this optimizing for you. So don't make your code less readable for no performance benefit. In general, compilers are much better than you think they are. –  flamingpenguin Nov 20 '12 at 11:41
@flamingpenguin I agree with your point, but the OP did ask if there was any more efficient way of doing the algorithm, and my little benchmarks indicated that storing the result would be slightly better for time efficiency. Also, I don't think my version loses any readability, but I guess that's a matter of personal preference. There are also different compilers, mind you, and they all cannot necessarily do all the same optimizations. Not that it really matters in this particular case, but anyway. –  ZeroOne Nov 20 '12 at 14:06

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.

• 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
-

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);
}
}

-