import axle.math._

Linear using foldLeft

fibonacciByFold(10)
// res0: Int = 89

Recursive

fibonacciRecursively(10)
// res1: Int = 89

Some alternatives that are not in Axle include

Recursive with memoization

val memo = collection.mutable.Map(0 -> 0L, 1 -> 1L)
// memo: scala.collection.mutable.Map[Int,Long] = Map(1 -> 1, 0 -> 0)

def fibonacciRecursivelyWithMemo(n: Int): Long = {
  if (memo.contains(n)) {
    memo(n)
  } else {
    val result = fibonacciRecursivelyWithMemo(n - 2) + fibonacciRecursivelyWithMemo(n - 1)
    memo += n -> result
    result
  }
}
// fibonacciRecursivelyWithMemo: (n: Int)Long

fibonacciRecursivelyWithMemo(10)
// res2: Long = 55

Recursive squaring

Imports

import axle._
import axle.jblas._
import spire.implicits._
import org.jblas.DoubleMatrix

implicit val laJblasDouble = axle.jblas.linearAlgebraDoubleMatrix[Double]
import laJblasDouble._

The fibonacci sequence at N can be generated by taking the Nth power of a special 2x2 matrix. By employing the general-purpose strategy for exponentiation called “recursive squaring”, we can achieve sub-linear time.

val base = fromColumnMajorArray(2, 2, List(1d, 1d, 1d, 0d).toArray)
// base: org.jblas.DoubleMatrix = [1.000000, 1.000000; 1.000000, 0.000000]

def fibonacciSubLinear(n: Int): Long = n match {
  case 0 => 0L
  case _ => exponentiateByRecursiveSquaring(base, n).get(0, 1).toLong
}
// fibonacciSubLinear: (n: Int)Long

Demo:

fibonacciSubLinear(78)
// res4: Long = 8944394323791464

Note: Beyond 78 inaccuracies creep in due to the limitations of the Double number type.