Last active
August 29, 2015 14:06
-
-
Save ashrithr/7e8bdc70b348deac6567 to your computer and use it in GitHub Desktop.
Scala Recursions and Tail call optimization
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import scala.annotation.tailrec | |
object fact { | |
// n! = n * (n-1) * (n-2) * ... * 2 * 1 | |
// n! = if (n>1) n * (n-1)! else 1 | |
def factorial(n: Int): Int = | |
if (n > 1) | |
n * factorial(n - 1) | |
else | |
1 | |
factorial(5) | |
factorial(10) | |
factorial(15) // this is not correct as INT has reached its limit it could hold upto 32 bit values | |
// long can store twice as long as int | |
def factorialLong(n: Long): Long = | |
if (n > 1) | |
n * factorialLong(n - 1) | |
else | |
1 | |
factorialLong(15) | |
factorialLong(20) | |
factorialLong(30) // does not work with greater values as long reached its limit | |
// bigint stores an arbitary number of bits, problem with bigint is that it is | |
// far slower because the system is hardwired to handle 32 bit int's | |
def factorialBig(n: BigInt): BigInt = | |
if (n > 1) | |
n * factorialBig(n - 1) | |
else | |
1 | |
factorialBig(30) | |
factorialBig(100) | |
/* | |
// results in stack overflow, as many JVMs limit the depth of recursion stack | |
// to be in limit to couple of thousand stack frames | |
factorialBig(10000) | |
*/ | |
/* | |
Factorial using tailrec (uses only one level stack frame) and run in constant | |
stack frame and to avoid stack overflow exceptions. | |
The interest of tail recursion is mostly to avoid very deep recursive chain. | |
*/ | |
def factorialTailRec(num: BigInt): BigInt = { | |
@tailrec | |
def calculate(accumulator: BigInt, number: BigInt): BigInt = | |
if (number == 0) | |
accumulator | |
else | |
calculate(accumulator * number, number - 1) | |
calculate(1, num) | |
} | |
factorialTailRec(10000) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// fibonnaci | |
def fib(n: Int): BigInt = { | |
def loop(n: Int, next: BigInt, acc: BigInt): BigInt = | |
if (n == 0) acc | |
else loop(n-1, acc + next, next) | |
loop(n, 1, 0) | |
} | |
//fibonnaci using memoization and streams | |
val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2) | |
scala> fib take 100 mkString " " | |
res22: String = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ... |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment