Instantly share code, notes, and snippets.

Embed
What would you like to do?
package io.github.cjwebb
import scala.annotation.tailrec
object Fibonacci extends App {
/** Get the nth fibonacci number */
def fib_iter(n: Int) = {
if (n < 2) n
else {
var ans = 0
var n1 = 0
var n2 = 1
var i = n - 1
while (i > 0) {
i = i - 1
ans = n1 + n2
n1 = n2
n2 = ans
}
ans
}
}
def fib_recur(n: Int): Int = {
n match {
case i if i < 2 => i
case i => fib_recur(n-1) + fib_recur(n-2)
}
}
def fib_tailrec(n: Int) = {
@tailrec
def rec(n: Int, a: Int, b: Int): Int= {
n match {
case 0 => b
case _ => rec(n-1, a+b, a)
}
}
rec(n, 1, 0)
}
/** Pass in n, to receive that many numbers */
def bad_fib(n: Int) = (0 to n-1) map (n => fib_tailrec(n))
def fib_acc(n: Int) = {
@tailrec
def acc(list: List[Int], i: Int): List[Int] = {
if (i >= n || n < 2) list
else {
val newList = list ::: List(list(i-1)+list(i-2))
acc(newList, i+1)
}
}
acc(List(0, 1), 2).take(n)
}
def fib_acc2(n: Int, s: List[Int] = List(1, 0)): List[Int] = {
if (n <= 2) s.reverse
else fib_acc2(n - 1, s(0) + s(1) :: s)
}
def fib_stream(n: Int) = {
lazy val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
fibs.take(n).toList
}
println((0 to 10) map (n => fib_recur(n)))
println((0 to 10) map (n => fib_iter(n)))
println((0 to 10) map (n => fib_tailrec(n)))
println(fib_acc2(10))
println(fib_stream(10))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment