# Recursive FizzBuzz

The FizzBuzz problem is a classical interview question used to quickly discard candidates that want to work as programmers but can’t actually write code. It is very simple and is based on an old mental exercise to help kids practice division.

The idea is to say (or print) the numbers from 1 to 100, except in three special cases:

- If the number is divisible by 3, then you must say «Fizz».
- If the number is divisible by 5, then you have to say «Buzz».
- Finally, if the number happens to be a multiple of both 5 and 3, then the word to say is «FizzBuzz».

## Naive implementation

To solve this problem is very easy. The following code, written in C, tackles it with a naive approach, using a loop and checking 3 conditions:

```
#include <stdio.h>
void fizzbuzz(int number);
int main(void)
{
int limit = 100;
fizzbuzz(limit);
}
void fizzbuzz(int number)
{
for(int current = 1; current <= number; current++)
{
int printnumber = 1;
if (current % 3 == 0)
{
printf("Fizz");
printnumber = 0;
}
if (current % 5 == 0)
{
printf("Buzz");
printnumber = 0;
}
if (printnumber) printf("%i", current);
printf("\n");
}
}
```

This is very uninteresting. Another common approach is to create a string and check if is empty in the last step, if so then print the corresponding number.

## Python version with lambda functions

We can use some trickery and write a shorter version in Python. Let’s see:

```
fizzbuzz = (
lambda n:
'Fizz' * (n % 3 == 0) +
'Buzz' * (n % 5 == 0) or
str(n))
if __name__ == "__main__":
number = 100
for number in range(1, number+1):
print(fizzbuzz(number))
```

This is way simpler and more elegant, but less obvious for someone not familiarized with some of the quirks of logical expressions and lambda functions.

Lambda functions are anonymous, often one-liner, throw away functions that
allow to simplify some code. It this case I used one that takes *n* as
parameter then checks if n is true or false and returns the result of that.
How so?

Well, if the reminder of n % 3 is zero then the expression inside parenthesis is True and, surprisingly can be treated as 1, hence we can multiply it by the string «Fizz». Yeah, crazy stuff, multiply strings by numbers that are actually booleans. Welcome to Python.

The same goes for the second line of the lambda function. But there’s
something else, that *or* has a special behavior too: if the left-hand
statement is False (an empty string or a 0 are treated as False), then it
returns its right hand side, in this case converts the corresponding number
into a string.

## Recursive version

A few days ago I was reading a book about javascript and found an example of recursion that was very interesting. Most of the examples one can find about recursion in introductory programming books are very simple: the factorial function, the power function, or the Fibonacci sequence. So I was gladly surprised to come across something different. Here’s that example slightly modified and refactored in Python:

```
def expand(number):
current, history = 1, "1"
def find(current, history):
if (current == number):
return history
elif (current > number):
return False
else:
return find(current * 2, history + " * 2") or \
find(current * 3, history + " * 3") or \
find(current * 5, history + " * 5")
return find(current, history)
```

This function takes a *number* that is divisible by either 2, 3 or 5, and
writes it is as an expansion of its factors. For example: 120 = 1 * 2 * 2 * 2 *
3 * 5.

What’s especial about this approach is that implementing a function that does not use recursion will probably result in a way more complex an far less elegant piece of code.

So it immediately hit me: «there are 5s and 3s in there, so it shouldn’t be hard to turn the FizzBuzz into a recursive function».

This is a recursive function combining the ideas from the two snippets above and solves the FizzBuzz problem:

```
def rfizzbuzz(number):
current, history = 0, ""
def find(current, history):
if (current == number):
return history
else:
return find(current + 1, history + (
"Fizz" * ((current + 1) % 3 == 0) +
"Buzz" * ((current + 1) % 5 == 0) or
str(current + 1)) + '\n')
return find(current, history)
```

The core of this does pretty much the same as the lambda version. The improvement in this case is that the recursion makes it unnecessary to use a loop and one can simply write: print(rfizbuzz(100)) and get the expected output.

## Further resources

Another interesting and funny sources where you can see unusual approaches to the FizzBuzz problem:

- This Enterprise Quality Code implementation. It is actually a satire,
mocking how making something
*Enterprise Quality*often makes it unnecessarily complex. - There’s also a quite interesting article whose author’s goal is to «have
the most beautiful code». It is a very serious approach, you can even tell by
the title:
*FizzBuzz in Haskell by Embedding a Domain-Specific Language*.