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.

You might want to look into Continuation Passing Style (CPS). — DaoWen, May 07 '15 at 23:31

score 6 · Accepted Answer · answered May 07 '15 at 23:09

6

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)
}

answered May 07 '15 at 23:09

Svante

50,694
11
78
122

Ok, I think that makes sense to me. Though not sure how/if I would have gotten there more generally. BTW, it does compile and works correctly. – JDesuv May 08 '15 at 00:30
It is quite similar to Fibonacci. – Svante May 08 '15 at 00:45

score 3 · Answer 2 · answered May 08 '15 at 00:55

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.

Convert normal recursion to tail recursion with multiple recursive calls

2 Answers2