Convert normal recursion to tail recursion with multiple recursive calls

Question

I am trying to understand how various recursive functions can be converted to tail recursive. I've looked through the many examples of both fibonacci and factorial conversions to tail recursive and understand those but am having a tough time making the leap to a problem with a somewhat different structure. An example is:

def countSteps(n: Int): Int = {
  if(n<0) return 0
  if(n==0) return 1
  countSteps(n-1) + countSteps(n-2) + countSteps(n-3)
}

How would you convert this to a tail recursive implementation?

I've looked through similar questions such as: Convert normal recursion to tail recursion But again these don't seem to translate to this problem.

Answer 1

Some things just are not tail recursive, and any attempt to transform them will end up building the stack manually.

In this case, however, we can accumulate (untested, don't have scala):

def countSteps(n: Int): Int = {
  if (n < 0) return 0
  countStepsAux(n, 0, 1, 0, 0)
}

def countStepsAux(n: Int, step: Int, n1: Int, n2: Int, n3: Int): Int = {
  if (n == step) return n1
  countStepsAux(n, step + 1, n1 + n2 + n3, n1, n2)
}