Fibonacci Tutorial with Java 8 Examples: recursive and corecursive

Calculating the Fibonacci suite is one of the ubiquitous examples we can find on the Internet. Most given examples, however are very bad. By the way, looking at all given examples would probably allow building a catalog of anti-patterns.

The main flaws we can find in these examples are:

Bad requirements interpretation

Requirements such as “Display the Fibonacci numbers from 1 to n” are very misleading. The reason is that there should be no relation between what we need to produce (an ordered collection of the Fibonacci numbers) and what we want to do with it (printing to the console). This leads to implementations such as:

public static void main(String args[]) {
   int n = 1000;
  for(int i = 1; i <= n; i++){
    System.out.print(fibonacci(i) +" ");
  }
}

public static int fibonacci(int number) {
  if (number == 1 || number == 2) {
    return 1;
  }
  return fibonacci(number - 1) + fibonacci(number - 2);
}

Obviously, this code has many flaws. One is that it mixes what is to be produced (a string of numbers) and what is to be done with this collection (print it to the console).

As programmers are asked to write reusable code, the program should have two parts: one producing the series, and the other one printing it.

Bugs

This code contains two main bugs:

Arithmetic overflow

For some values, this program will not produce any error, but the result will quickly (and silently) overflow. This program will then produce a series of alternating positive and negative values.

This programs overflows for f(47) = -1323752223. A really low limit!

Stack overflow

This program uses recursion. Java is not a true recursive language, since the recursion depth is limited by the stack size. So, this program will blow the stack quite quickly. On my (standard) configuration, it overflows the stack for f(6222). This may be changed by increasing the stack size, but it is generally a bad solution because all threads will use the increased stack size, even if they do not need it.

Performance

When it does not overflow the stack, this program is extremely slow because the whole suite is recalculated for each new number. Worst, each call contains two recursive calls, so the time needed will grow exponentially. It is interesting to note that if the stack overflows, the program crashes very quickly. For example, for n = 7000, it crashes within a few milliseconds. However, for n = 6000, it does not crash, but it is so slow that it will probably never finish!

How to solve these problems

Arithmetic overflow

To handle this problem, we will simply use BigInteger instead of int. This way, we will only be limited by memory capacity.

Stack overflow

There are two solutions to the stack overflow problem. The first one is to store the intermediate calculations (lazily evaluated) on the heap, going backward (starting with n, then n-1, n-2) until the terminal condition is found, and then going back in reverse order, evaluating the result. This is (relatively) simple to do for a tail recursive call. A tail recursive function is a function in which the recursive call appears as the last operation. But the trivial version of the Fibonacci function is not tail recursive for two reasons: there are two recursive calls (they can't both be the last operation!) and anyway, the last operation is the addition of the results of these calls. So we would first have to transform the function into a tail recursive one.

This is not difficult, and we could do it like this:

public static BigInteger fibTail(int x) {
  return fibTailHelper(BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(x));
}

public static BigInteger fibTailHelper(BigInteger acc1, BigInteger acc2, BigInteger x) {
  if (x.equals(BigInteger.ZERO)) {
    return BigInteger.ONE; 
  } else if (x.equals(BigInteger.ONE)) {
    return acc1.add(acc2);
  } else {
    return fibTailHelper(acc2, acc1.add(acc2), x.subtract(BigInteger.ONE));
  }
}

However, while this is now tail recursive, we still have to implement recursion using the heap in order to avoid stack overflow.

Note that beside allowing (relatively) easy heap optimization, this version also offers a huge increase in performance. For example, it allows calculating until the stack overflow in less than 5 seconds. (I never had enough patience to let the normal recursive version run until the end when it does not overflow the stack.)

For tail call optimization, we'll use the following interface:

public interface RecCall<T> {

  RecCall<T> next();

  default boolean isDone() {
    return false;
  }

  default T getValue() {
    throw new IllegalStateException();
  }

  default T apply() {
    return Stream.iterate(this,RecCall::next)
                 .filter(RecCall::isDone)
                 .findAny()
                 .get()
                 .getValue();
  }

  public static <T> RecCall<T> cont(final RecCall<T> nextCall) {
    return nextCall;
  }

  public static <T> RecCall<T> stop(final T value) {
    return new RecCall<T>() {

      @Override
      public boolean isDone() {
        return true;
      }

      @Override
      public T getValue() {
        return value;
      }

      @Override
      public RecCall<T> next() {
        throw new IllegalStateException();
      }
    };
  }
}

Here is how this interface may be used:

private static BigInteger fibonacciTailRecursive(int number) {
  return fibonacciTailRecursiveHelper2(BigInteger.ONE, BigInteger.ZERO, 
                BigInteger.valueOf(number)).apply();
}

private static <T> RecCall<BigInteger> fibonacciTailRecursiveHelper(BigInteger acc1, BigInteger acc2, BigInteger x) {
  if (x.equals(BigInteger.ZERO)) {
    return RecCall.stop(BigInteger.ONE);
  } else if (x.equals(BigInteger.ONE)) {
    return RecCall.stop(acc1.add(acc2));
  } else {
    return RecCall.cont(() -> fibonacciTailRecursiveHelper(acc2, acc1.add(acc2),  x.subtract(BigInteger.ONE)));
  }
}

Another way to go is to use iteration, such as this example (also found on the Internet as an example of how to solve the Fibonacci problem). I have just replaced int with BigInteger in order to avoid arithmetic overflow:

public static BigInteger fibonacciIterative(int number) {
  if (number == 1 || number == 2) {
    return BigInteger.ONE;
  }
  BigInteger fibo1 = BigInteger.ONE;
  BigInteger fibo2 = BigInteger.ONE;
  BigInteger fibonacci = BigInteger.ZERO;
  for (int i = 3; i <= number; i++) {
    fibonacci = fibo1.add(fibo2);
    fibo1 = fibo2;
    fibo2 = fibonacci;
  }
  return fibonacci;
}

We could use any of these solutions. Of course, the recursive version may seem more complicated. (But it is also more interesting!) So are we done? Not so. To meet our requirement, we have to build a string of the Fibonacci numbers from 1 to n. In the first naive approach, each number was printed to the console as soon as being calculated. These two examples give the value of f(n). A naive again approach would be to call one of this functions with argument varying from 1 to n, such as:

public static String fibonacciIterativeSuite(int number) {
  return IntStream.rangeClosed(1, number)
      .boxed()
      .map(i -> fibonacciIterative(i))
      .map(BigInteger::toString)
      .collect(Collectors.joining(", "));
}

or

public static String fibonacciTailRecursiveSuite(int number) {
  return IntStream.rangeClosed(1, number)
      .boxed()
      .map(i -> fibonacciTailRecursive(i))
      .map(BigInteger::toString)
      .collect(Collectors.joining(", "));
}

Both of these approach work, and they have near to equivalent performance. For example, calling each method to get the Fibonacci numbers form 1 to 10 000 give the following results:

//
//
Time needed to calculate Fibonacci numbers up to 10_000 iterative:17125
Time needed to calculate Fibonacci numbers up to 10_000 tail recursive:19869

The main problem here is performance. This poor performance is due to several reasons. For the iterative version, the algorithm is clearly bad. The method calculating f(n) is called n times, but each call implies in fact a recalculation of the preceding values, although not in the form of a method call. This is clearly related to the definition: f(n) = f(n – 1) + f(n – 2). This means that to calculate f(n), we need to calculate f(n – 1) and f(n -2). In other word, we should have only one method call and this method should accumulate the intermediate results. This is something that looks like memoization although it is a bit different since the intermediate results are not the direct result of the method call.

By contrast, the recursive version clearly needs memoization. Each call to f(n) clearly implies a call to f(n – 1).

At this point, we may realize why the tail recursive version is much faster than the original recursive (but not tail recursive) one: a call to the tail recursive f(n) implies a call to f(n – 1) which means a total of n calls. By contrast, a call to the non tail recursive version of f(n) implies to calls: f(n – 1) and f(n – 2). The total number of call is thus 2^ⁿ.

But we have another problem: we are calling the function not only for n, but for all values between 1 and n. Clearly, we would benefit from storing the previous values somewhere in order not to have to calculate them several times. This is memoization.

Note that memoization is a form of caching. Memoization is caching, but caching is not always memoization. With memoization, a pure function remains pure. Storing the values in an external (shared) map would probably gives even better optimization, but we would have to handle concurrent access.

Solutions for memoization

We could store the calculated values in a map and pass the map as an additional parameter to the helper function. However, we do not need this here if we look at the requirements: we need to build a String with all Fibonacci numbers in ascending order. So we are only calculating Fibonacci numbers in ascending order and we need only pass the two last values as parameters. For the rest, we may accumulate the result in some convenient structure such as List, or even a StringBuilder. Here is the result for the iterative version:

public static String fibonacciIterativeMemoized(int number) {
  switch(number) {
    case 0:
      return "1";
    case 1:
      return "1, 1";
    default:
      BigInteger fibo1 = BigInteger.ONE;
      BigInteger fibo2 = BigInteger.ONE;
      BigInteger fibonacci = BigInteger.ZERO;
      StringBuilder builder = new StringBuilder("1, 1, ");
      for (int i = 2; i <= number; i++) {
        fibonacci = fibo1.add(fibo2);
        builder.append(fibonacci).append(", ");
        fibo1 = fibo2;
        fibo2 = fibonacci;
      }
      return builder.toString();
  }
}

(Note that to keep it simple, we do not handle the problem of the last delimiter.)

This method is very similar to non memoized one. The major difference is that we do not need to call it 10 000 times. One time is enough!

For the tail recursive version, the problem is much more severe: not only we call the function once for each value between 1 and n, but each call implies n recursive calls. The end result is approximately n²/2 calls! Using memoization will solve this problem:

public static String fibonacciTailRecursiveMemoized(int number) {
  return fibonacciTailRecursiveMemoizedHelper(new StringBuilder(), BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(number)).apply().toString();
}

private static <T> RecCall<StringBuilder> fibonacciTailRecursiveMemoizedHelper(StringBuilder acc, BigInteger acc1, BigInteger acc2, BigInteger x) {
  if (x.equals(BigInteger.ZERO)) {
    return RecCall.stop(acc);
  } else if (x.equals(BigInteger.ONE)) {
    return RecCall.stop(acc.append(acc1.add(acc2)).append(", "));
  } else {
    return RecCall.cont(() -> fibonacciTailRecursiveMemoizedHelper(acc.append(acc1.add(acc2)).append(", "), acc2, acc1.add(acc2), x.subtract(BigInteger.ONE)));
  }
}

With this version, the function is called only n times.

And now for performance:

//
//
Time needed to calculate Fibonacci numbers up to 10_000 iterative with memoization:1501
Time needed to calculate Fibonacci numbers up to 10_000 tail recursive with memoization:1515

We can see that the recursive version is as fast as the iterative version. Both are much faster than the non memoized ones.

Another (better) approach

We may consider the problem in a very different way. Instead of a suite of numbers, we could consider a suite of pairs (tuples) such as transforming:

1, 1, 2, 3, 5, 8, 13, 21, ...

into

(1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), ...

Each tuple may be constructed from the previous one. The second element of tuple n becomes the first element of tuple n + 1. The second element of tuple n + 1 is equal to the sum of the two elements of tuple n. In Java, we may write a function for this:

x -> new Tuple<>(x._2, x._1.add(x._2)

given the following Tuple class:

class Tuple<T, U> { 
  public final T _1; 
  public final U _2; 
  public Tuple(T t, U u) { 
    this._1 = t; 
    this._2 = u; 
  } 
}

We can now write a very simple, accurate and (relatively) efficient implementation of our program:

private static long number = 1000; 

public static void main(String[] args) { 

  Tuple<BigInteger, BigInteger> seed = new Tuple<>(BigInteger.ONE, BigInteger.ONE);

  UnaryOperator<Tuple<BigInteger, BigInteger>> f = x -> new Tuple<>(x._2, x._1.add(x._2));

  Stream<BigInteger> fiboStream = Stream.iterate(seed, f)
       .map(x -> x._1)
       .limit(number);
} 

This program uses the iterate method of the Stream class to create a Stream<Tuple> starting with the seed value (1, 1) and applying our function to calculate the next element. This creates an infinite stream, which is not a problem since it is lazily evaluated.

We then map to this stream a function from a tuple to its first element.

Eventually, we apply the chosen limit (which does not have any effect until the stream is evaluated).

Now, if we want to display the result as a string of values separated by commas, we just have to do the following:

String result = fiboStream.map(BigInteger::toString).collect(Collectors.joining(", ")); 
System.out.println(result);

This, by the way, is the same approach as the iterative version and is called "corecursion". It it the inverse of recursion. When recursion starts from the end, corecursion starts from the beginning. This is what the iterate method of the Stream class is about. (Note that this method is sometimes called unfold because it is the inverse of fold. But in Java 8, fold is called reduce!)

One can also remark that using tuples is exactly what we are doing in the tail recursive version, although implicitely, since we do not need to return tuples, but only to pass them as arguments to each recursive call. Instead of taking one integer as an argument and returning two, we pass three integers on each recursive call.

Performance

It is difficult to talk about performance. This is because the stream is lazily evaluated. So it is not possible to measure the evaluation time separately from the time spent to “use” the result (here to build a String). However, it does not really matter. What is important is the overall performance compared to the other solutions:

//
//
Time needed to calculate Fibonacci numbers up to 10_000 corecursive:1733
Time needed to calculate Fibonacci numbers up to 10_000 iterative with memoization:1501
Time needed to calculate Fibonacci numbers up to 10_000 tail recursive with memoization:1515

We can see that although it is slightly slower than the two other solutions, it is so simple and so clean that choosing anything else would be premature optimization. The only regret we may have is that the Tuple class is not part of standard Java. We would even like to have syntactic sugar above this class such as what is offered by other languages, where Tuple<Integer, Integer>(x, y) is simply written (x, y)! Of course, we also may regret that Java is not able to do TCO (Tail Call Optimization) automatically.