When to use auxiliary recursive functions/methods for recursive functions/methods

user_9454522 0
Viewed 1142

In a worksheet for a functional programming course, I was asked to write a function in Scala (though I think the prof may have meant method) that recursively prints elements in a list on a new line with a line number with a result like this:

    scala> printCounter (List ("the", "rain", "in", "spain"))
[001] the
[002] rain
[003] in
[004] spain

The solution provided on the worksheet looks like this:

def printCounterAux [X] (xs:List[X], count:Int) : Unit = {
  xs match {
    case Nil   => ()
    case y::ys => {
      println ("[%03d] %s".format (count, y))
      printCounterAux (ys, count + 1)
    }
  }
}

def printCounter [X] (xs:List[X]) : Unit = {
  printCounterAux (xs, 1)
}

printCounter (List ("the", "rain", "in", "spain"))

It had not occurred to me to create an auxiliary method. My question, as someone who is still getting a handle on recursion, is: how do you know when it is necessary to create an auxiliary recursive method? In this case would the signal be multiple parameters? Or is it simply a matter of lots of exposure to these kinds of methods? Thanks very much for any advice you can share. Cheers.

recursion scala
2 Answers

printCounterAux has a different API than printCounter. Not only that, but the change in the API has nothing to do with the functionality of the method, it is purely an implementation detail. (For example, had printCounter been implemented with a loop, it wouldn't be necessary.)

Therefore, you want to hide this API from the consumer.

In order to really, properly hide this API, printCounterAux should however be an inner function of printCounter, like so:

def printCounter[X](xs: List[X]): Unit = {
  printCounterAux()

  def printCounterAux[X](xs: List[X] = xs, count: Int = 1): Unit = xs match {
    case Nil     => ()
    case y :: ys => {
      println("[%03d] %s".format(count, y))
      printCounterAux(ys, count + 1)
    }
  }
}

printCounter(List("the", "rain", "in", "spain"))

Note that in many cases, you will need to carry some sort of "state" around with you, and in a recursive function in a purely-functional language, a very convenient place to carry that state is in the arguments of the function. Therefore, you will often have to modify the parameter list in order to add a state parameter (like count in this case), which shouldn't be exposed to the consumer.

user_29880

It’s common in Scala to write functions that are local to the body of another function. In functional programming, we shouldn’t consider this a bigger deal than local integers or strings.

The way we write loops functionally, without mutating a loop variable, is with a recursive function. Here we’re defining a recursive helper function inside the body of the factorial function. Such a helper function is often called go or loop by convention.

def factorial(n: Int): Int = {
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

Since it’s local, the go function can only be referred to from within the body of the factorial function, just like a local variable would. The definition of factorial finally just consists of a call to go with the initial conditions for the loop.

The arguments to go are the state for the loop. In this case, they’re the remaining value n, and the current accumulated factorial acc. To advance to the next iteration, we simply call go recursively with the new loop state (here, go(n-1, n*acc)), and to exit from the loop, we return a value without a recursive call (here, we return acc in the case that n <= 0). Scala detects this sort of self-recursion and compiles it to the same sort of bytecode as would be emitted for a while loop(we can write while loops by hand in Scala, but it’s rarely necessary and considered bad form since it hinders good compositional style.), so long as the recursive call is in tail position.

A call is said to be in tail position if the caller does nothing other than return the value of the recursive call. For example, the recursive call to go(n-1,n*acc) is in tail position, since the method returns the value of this recursive call directly and does nothing else with it. On the other hand, if we said 1 + go(n-1,n*acc), go function would no longer be in tail position, since the method would still have work to do when go returned its result (namely, adding 1 to it). If all recursive calls made by a function are in tail position, Scala automatically compiles the recursion to iterative loops that don’t consume call stack frames for each iteration and we can avoid StackOverflow issues. By default, Scala doesn’t tell us if tail call elimination was successful, but if we’re expecting this to occur for a recursive function we write, we can tell the Scala compiler about this assumption using the tailrec annotation , so it can give us a compile error if it’s unable to eliminate the tail calls of the function.

def factorial(n: Int): Int = {
    @annotation.tailrec
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

This is a very common scenario to write an inner function, or local definition.

user_85714980
Related