Created
December 25, 2016 15:17
-
-
Save samuelreh/9d06344b3c07a229c0502a08ad999b21 to your computer and use it in GitHub Desktop.
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 com.scalakata._ | |
@instrument class Playground { | |
/* Tail Recursion: | |
* | |
* The following recursive function calculates the fibonocci number for the given index. With a large enough index, | |
* the program will throw a StackOverflowError. | |
*/ | |
def fib(n: Int): Int = { | |
if (n > 2) fib(n - 1) + fib(n - 2) | |
else 1 | |
} | |
assert((1 to 6).map(fib(_)) == List(1,1,2,3,5,8)) | |
/* Here is the start of a tail recursive version of the fib sequence, | |
* Finish the implementation by filling in the ???s: | |
*/ | |
def tailrecFib(n: Int): Int = { | |
@annotation.tailrec | |
def iter(remaining: Int, curr: Int, prev: Int): Int = { | |
if (remaining <= 1) ??? | |
else iter(???, ???, ???) | |
} | |
iter(n, 1, 0) | |
} | |
assert((1 to 6).map(tailrecFib(_)) == List(1,1,2,3,5,8)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment