Skip to content

Instantly share code, notes, and snippets.

@samuelreh
Created December 25, 2016 15:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save samuelreh/9d06344b3c07a229c0502a08ad999b21 to your computer and use it in GitHub Desktop.
Save samuelreh/9d06344b3c07a229c0502a08ad999b21 to your computer and use it in GitHub Desktop.
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