Understanding tail-recursion

Add the following tests underneath the previous one:

"RetCalc.nbOfMonthsSaving" should {
"calculate how long I need to save before I can retire" in {...}

"not crash if the resulting nbOfMonths is very high" in {
val actual = RetCalc.nbOfMonthsSaving(
interestRate = 0.01 / 12, nbOfMonthsInRetirement = 40 * 12,
netIncome = 3000, currentExpenses = 2999, initialCapital = 0)
val expected = 8280
actual should ===(expected)
}

"not loop forever if I enter bad parameters" in pending

We will implement the not loop forever later on. It is a good practice to write pending tests as soon as you think about new edge cases or other use cases for your function. It helps to keep a direction toward the end goal, and gives some momentum—as soon as you have made the previous test pass, you know exactly what test you need to write next.

Run the test, and it will fail with StackOverflowError. This is because each time loop is called recursively, local variables are saved onto the JVM stack. The size of the stack is quite small, and as we can see, it is quite easy to fill it up. Fortunately, there is a mechanism in the Scala compiler to automatically transform tail-recursive calls into a while loop. We say that a recursive call (the call to the loop function inside the loop function) is tail-recursive when it is the last instruction of the function.

We can easily change our previous code to make it tail-recursive. Select returnValue, and hit cmd + O to inline the variable. The body of the loop function should look like this:

@tailrec
def
loop(months: Int): Int = {
val (capitalAtRetirement, capitalAfterDeath) = simulatePlan(
interestRate = interestRate,
nbOfMonthsSaving = months, nbOfMonthsInRetirement =
nbOfMonthsInRetirement,
netIncome = netIncome, currentExpenses = currentExpenses,
initialCapital = initialCapital)

if (capitalAfterDeath > 0.0)
months
else
loop(months + 1)

IntelliJ changed the small symbol in the editor's margin to highlight the fact that our function is now tail-recursive. Run the test again and it should pass. It is a good practice to also put an annotation @tailrec before the function definition. This tells the compiler that it must verify that the function is indeed tail-recursive. If you annotate a @tailrec function that is not tail-recursive, the compiler will raise an error.

When you know that the depth of a recursive call can be high (more than 100), always make sure it is tail-recursive.
When you write a tail-recursive function, always annotate it with @tailrec to let the compiler verify it.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset