Questions And Answers

More Tutorials

Scala Recursion


Tail Recursion

Using regular recursion, each recursive call pushes another entry onto the call stack. When the recursion is completed, the application has to pop each entry off all the way back down. If there are much recursive function calls it can end up with a huge stack.

Scala automatically removes the recursion in case it finds the recursive call in tail position. The annotation (@tailrec) can be added to recursive functions to ensure that tail call optimization is performed. The compiler then shows an error message if it can't optimize your recursion.

Regular Recursion

This example is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns.

def fact(i : Int) : Int = {
 if(i <= 1) i
 else i * fact(i-1)

The function call with the parameter will result in a stack that looks like this:

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))

If we try to annotate this example with @tailrec we will get the following error message: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Tail Recursion

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step.

def fact_with_tailrec(i : Int) : Long = {
 def fact_inside(i : Int, sum: Long) : Long = {
 if(i <= 1) sum
 else fact_inside(i-1,sum*i)

In contrast, the stack trace for the tail recursive factorial looks like the following:

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

There is only the need to keep track of the same amount of data for every call to fact_inside because the function is simply returning the value it got right through to the top. This means that even if fact_with_tail 1000000 is called, it needs only the same amount of space as fact_with_tail 3. This is not the case with the non-tail-recursive call, and as such large values may cause a stack overflow.

Stackless recursion with trampoline(scala.util.control.TailCalls)

It is very common to get a StackOverflowError error while calling recursive function. Scala standard library offers TailCall to avoid stack overflow by using heap objects and continuations to store the local state of the recursion.

Two examples from the scaladoc of TailCalls

import scala.util.control.TailCalls._
def isEven(xs: List[Int]): TailRec[Boolean] =
 if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
def isOdd(xs: List[Int]): TailRec[Boolean] =
 if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))
// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result
def fib(n: Int): TailRec[Int] =
 if (n < 2) done(n) else for {
 x <- tailcall(fib(n - 1))
 y <- tailcall(fib(n - 2))
 } yield (x + y)
// What is the 40th entry of the Fibonacci series?


In this page (written and validated by ) you learned about Scala Recursion . What's Next? If you are interested in completing Scala tutorial, your next topic will be learning about: Scala Reflection.

Incorrect info or code snippet? We take very seriously the accuracy of the information provided on our website. We also make sure to test all snippets and examples provided for each section. If you find any incorrect information, please send us an email about the issue:

Share On:

Mockstacks was launched to help beginners learn programming languages; the site is optimized with no Ads as, Ads might slow down the performance. We also don't track any personal information; we also don't collect any kind of data unless the user provided us a corrected information. Almost all examples have been tested. Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness of all content. By using, you agree to have read and accepted our terms of use, cookies and privacy policy.