Efficient Recursive Fibonacci

2 points

9 years ago

A thought I wanted to share:

As a programming beginner you often get in touch with fibonacci to explain recursion:

  def fib1(n: Int): Int = {
    if (n <= 1) n
    else fib1(n - 1) + fib1(n - 2)
  }

And then you get told that this is simple but very inefficient. You see an efficient loop implementation afterwards and agree.

I think that this could give the impression to a lot of beginners that recursion is inefficient in general (it was like that for me). So recently I thought of an efficient and simple tail-recursive fibonacci implementation and came up with this one:

  def fib2(n: Int, a: Int = 0, b: Int = 1): Int = {
    if (n == 0) a
    else fib2(n - 1, b, b + a)
  }

I think this is simple enough as well and could help to introduce recursion to beginners without the wrong impressions.

(The examples are written in Scala and can be tested online here: https://scastie.scala-lang.org/iushI0EXSHy51MPXsFZOUQ. If you don't know the formula of Moivre/Binet, this is interesting as well: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)

4 comments