The trick to turning your function, or any function that requires multiple calls to itself into a tail recursive function is to break down the multiple calls into a list of arguments that can be recursively consumed and applied:
def countSteps(n: Int): Int = { def countSteps2(steps: List[Int], acc: Int): Int = steps match { case Nil => acc case head :: tail => val (n, s) = if (head < 0) (0, Nil) else if (head == 0) (1, Nil) else (0, List(head - 1, head - 2, head - 3)) countSteps2(s ::: tail, n + acc) } countSteps2(List(n),0) }
The inner function countSteps2 no longer takes a single argument but a list of arguments and an accumulator. This way we can calculate the value for the head of the arguments or generate a new list of arguments than can be added to the existing sequence to have countSteps2 recurse on.
Each time we do have an input, we take the head and compute either a 0, 1 or additional list of arguments. Now we can just recurse on countSteps2 again with the new list of arguments prepended to the existing tail and any value we did calculate added to the accumulator, acc. Since the only call to countSteps2 is an exit condition, the recursion is a tail recursion
We can finally exit when all inputs have been consumed, at which time acc has the results of all the recursive steps summed in it.
