The FizzBuzz problem. Let’s make it recursive

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, but when a number is divisible by 3 you must say «Fizz» instead of the number itself, and when the number is divisible by 5 you have to say «Buzz». When the number happens to be a multiple of both 5 and 3 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 probably 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 we use 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. 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 will be 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.