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