August 2018 Archives

I’ve just read yet another article showing how to calculate elements of the Fibonacci sequence in some functional language. I’ll give examples in Scala, though I’m not doing anything very clever linguistically, so they shouldn’t be hard for anyone. Of course, it showed the hopelessly inefficient dual recursion

def terrible_fib(n: BigInt): BigInt =
  if (n < 0) sys.error("not defined for -ve n")
  else if (n == 0) 0
  else if (n == 1) 1
  else terrible_fib(n - 1) + terrible_fib(n - 2)

and a tail-recursive version

def tail_fib0(n: BigInt, a: BigInt, b: BigInt): BigInt =
  if (n == 0) a
  else tail_fib0(n - 1, a + b, a)
def tail_fib(n: BigInt): BigInt =
  if (n < 0) sys.error("not defined for -ve n")
  else tail_fib0(n, 0, 1)

There was also an explicitly iterative version, which isn’t interestingly different from the tail-recursive version, so I shan’t bother showing it. Unfortunately, the tail-recursive version is still rather slow. On my (very old) laptop, it takes nearly a minute to calculate tail_fib(1000000). We can do much better.