How to optimize Scala double Call of Recursive Function

Question

I'm trying to get this Recursive Function to work:

@tailrec
def rec(n: BigInt): BigInt = {
  if (n == 0) 0
  else if (n == 1) 1
  else (rec(n - 1) + rec(n - 2))
}

Error:(13, 24) could not optimize @tailrec annotated method rec: it contains a recursive call not in tail position else (rec(n - 1) + rec(n - 2))

How can this be optimized to work with tailrec?

Luka Jacobowitz Luka Jacobowitz · Accepted Answer · 2017-03-10T11:03:08

You're going to have to write a tail recursive helper function:

def rec(n: BigInt): BigInt = {
  @tailrec 
  def helper(n: BigInt, previous: BigInt, next: BigInt): BigInt = {
    if (n == 0) previous
    else if (n == 1) next
    else helper(n - 1, next, (next + previous))
  }
  helper(n,0,1)
}

This is, so you can pass the previous and next values of your sequence to the function, thereby allowing you to get only one call to your function.

This is a common pattern, as many recursive algorithms can only be made tail recursive through additional control flow mechanisms (for example: continuation passing). Factorial is another great example, where writing a helper function with an extra parameter is needed to make it tail recursive.

How to optimize Scala double Call of Recursive Function

1 Answers