Last active
June 18, 2020 11:37
-
-
Save LukeDefeo/bf78c2fccaf99919640e58210d2360ad to your computer and use it in GitHub Desktop.
Tail recursion in scala explainer
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
def sumNonTail(ints: List[Int]): Int = { | |
ints match { | |
case Nil => 0 | |
case x :: xs => x + sumNonTail(xs) | |
} | |
// bytecode | |
// temp = sumNonTail(i) <-- recursive call not in tail position, the result of the recursive call is being 'post-processed' and has to be stored on the stack as it cant return out | |
// return x + temp | |
} | |
//to refactor move the variables that would be stored on stack to be function args as 'accumulator vars' | |
@tailrec | |
def sumTail(ints: List[Int], acc: Int = 0) : Int = { | |
ints match { | |
case Nil => acc | |
case x :: xs => sumTail(xs, acc + x) // sum tail is in tail position | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment