Geek Answers Handbook

Convert normal recursion to tail recursion with multiple recursive calls

I am trying to understand how various recursive functions can be converted to tail recursive. I looked through a lot of examples of both fibonacci and factorial transforms with tail recursive and understand them, but I have a hard time to jump to the problem with a slightly different structure. Example:

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 recursive tail implementation?

I looked at similar questions, such as: Convert normal recursion to tail recursion But again, they don't seem to go into this problem.

+4
source share
2 answers

, .

, , (, 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)
}
+4

, , , , :

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

countSteps2 , . , , , countSteps2.

, , head 0, 1, . countSteps2 , tail, , , , acc. countSteps2 ,

, , , acc , .

+3

More articles:


All Articles