Optimizing recursion — 2 Link to heading

In the previous article, we looked at how we can convert a vanilla recursive factorial implementation into tail-recursion to allow compilers to optimize and convert into iterative implementation. Today, we will look at a bit more real-world problem: Fibonacci sequence.

Vanilla Implementation Link to heading

Fibonacci sequence is one of the most well-known classic example of recursion, as it is defined as a recursive relation

Let’s translate the definition directly into Haskell and calculate the sequence at n = 50

fibo :: Integer -> Integer
fibo n =
  if n <= 1
    then n
    else fibo (n - 1) + fibo (n - 2)

main = do
  n <- readLn
  putStrLn $ show $ fibo n

It takes whopping 3,040 seconds to calculate fibo 50. This proves how inefficient the vanilla implementation is.

Optimized Recursion Link to heading

Let’s figure out why it is so slow. We can start by analyzing the time complexity of our implementation. For any given n ≥ 2, we call fibo(n-1) and fibo(n-2) recursively. Let’s suppose the time complexity for fibo(n) is T(n). The following recursive relation describes the time complexity

T(n+1) = T(n) + T(n-1)

This is indeed a Fibonacci sequence in itself. We can find an upper bound by substituting T(n-1) with T(n), since T(n-1) ≤ T(n) for all n. Then, we can easily see the time complexity upper bound is T(n) ≤ O(n²).

So, this is why our implementation is extremely slow and inefficient. What can we do? Now that we know the problem arises from the fact that we need to call both fibo (n-1) and fibo (n-2). Can we combine these into a single recursive call? Absolutely!

Let us define a helper function that returns the current and previous Fibonacci numbers.

-- returns fibo(n) and fibo(n-1)
fiboTwoAtOnce :: Integer -> (Integer, Integer)
fiboTwoAtOnce 0 = (0, 0) -- ignore the second number
fiboTwoAtOnce 1 = (1, 0)
fiboTwoAtOnce n =
  let (a, b) = fiboTwoAtOnce (n - 1)
   in (a + b, a)

main = do
  n <- readLn
  putStrLn $ show $ fibo n

Notice for each recursion step, we only call itself once. Its runtime is now 0.003 second, which is 1 million times more efficient than the vanilla implementation!

Are we done? Link to heading

This is already quite promising, but as we discussed before, a non-tail recursive implementation may yield issues, such as stack overflow. Indeed, the resident set size (RSS), a good proxy to memory footprint of the program, grows fast with respect to n. Below shows benchmark test of this version.

   n    | Time (s) | RSS (kB)
--------+----------+----------
1000    |   0.00   |    3.4
10000   |   0.00   |    5.6
100000  |   0.15   |   66.6
1000000 |  19.18   |  218.8

This is not what we would want. We need to implement the Fibonacci sequence in a way that its space complexity does not grow too fast.

Tail-Recursion Link to heading

Again, tail-recursion is to the rescue. Imagine writing Fibonacci function in a language that supports a loop, say Rust. Here is how we can implement efficiently using a simple loop

fn fibo(n: u64) -> u64 {
  if n == 0 {
    return 0;
  }

  let mut cur = 1;
  let mut prev = 0;
  for _ in 1..n {
    let sum = cur + prev;
    prev = cur;
    cur = sum;
  }
  cur
}

We can take this iterative code and convert it into tail-recursion.

helper :: Integer -> Integer -> Integer -> Integer
helper cur prev 0 = cur
helper cur prev n = helper (cur + prev) cur (n - 1)

fibo :: Integer -> Integer
fibo 0 = 0
fibo n = helper 1 0 (n - 1)

main = do
  n <- readLn
  putStrLn $ show $ fibo n

With this, let’s re-run our benchmark

   n    | Time (s) | RSS (kB)
--------+----------+----------
1000    |   0.00   |    3.2
10000   |   0.00   |    4.2
100000  |   0.02   |    7.2
1000000 |   1.85   |    7.6

We can observe that the tail-recursive implementation runs 10x faster and consumes 28x less memory than non-tail recursive one. That is a big difference.

The conclusion is that one should always strive to write a tail-recursive function. Not only will it run faster but also reduce memory footprint and prevent unexpected crash due to stack overflow.