4 ms·
Efficient Recursive Fibonacci
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)
- cousin_it 9y agoComputing Fibonacci numbers using only addition is very slow. Here's a much faster algorithm that uses multiplication: fibonacci n = fst (fib n) where fib 0 = (0, 1) fib n = if even n then (c, d) else (d, c + d) where (a, b) = fib (div n 2) (c, d) = (a * (b * 2 - a), a * a + b * b)
- manx 9y agoInteresting, thank you for sharing. Though my main concern was more about introduction to recursion without an exponential algorithm.
- al2o3cr 9y agoThe tail-recursive form is more efficient, but requires a lot more understanding of the problem to follow how one gets from the mathematical definition to the code. If you're teaching a language that emphasizes tail-call optimization, it's valuable to cover an even simpler case like factorial in detail. A function like "fib2" above is then a further demonstration of how to transform code into tail-call form.
- dozzie 9y ago> And then you get told that this is simple but very inefficient. You see an efficient loop implementation afterwards and agree. And then you're shown that a function can return a tuple. -module(fib). -export([fib/1]). fib(N) -> {A, _} = fib2(N), A. fib2(1) -> {1, 0}; fib2(N) -> {A, B} = fib2(N - 1), {A + B, A}.