官术网_书友最值得收藏!

Tail recursion to the rescue

There is a technique, an optimization really, that helps us get out of the logjam. However, we need to tweak the code a bit for this. We will make the recursive call as the last and only call. This means that there is no intermediate context to remember. This last and only call is called the tail call. Code in this tail call form is amenable to TCO. Scala generates code that, behind the scenes, uses a loop—the generated code does not use any stack frames:

import 
scala.annotation.tailrec

def count(list: List[Int]): Int = {
 @tailrec // 1
 def countIt(l: List[Int], acc: Int): Int = l match 
{
 
 case Nil => acc // 2
 case head :: tail => countIt(tail, acc+1) // 3 
 }
 countIt(list, 0)
}

The changes are like this:

We have a nested workhorse method that is doing all the hard work. The count method calls the countIt nested recursive method, with the list it got in the argument, and an accumulator. The earlier intermediate context is now expressed as an accumulator expression with the help of the following steps:

  1. The @tailrec annotation makes sure that we are doing the right things so that we benefit from the TCO. Without @tailrec, Scala may apply the optimization or it may not. The @tailrec annotation is a helping hand to ensure that the function call is optimized. Try the same annotation on our first version. You will get a compilation error.
  2. Play time: Change the second case in the previous code as shown:
    case head :: tail => {
    
     val cnt: Int = countIt(tail, acc + 1)
    
     println(cnt) 
    
     cnt 
    
    }
    
  3. You will get a compilation error after changing the second case:
    Error: could not optimize @tailrec annotated method countIt: it contains a recursive call not in tail position
    
  4. When the execution lands in this clause, we are at the end of the list. We are not going to find any more elements, so the base case just returns the accumulator.
  5. There is no intermediate context now—just a tail call. This is the only and last recursive call. We found one more element. We increment the accumulator to record the fact and pass it on.

Compared to the earlier version, why does this version work? If the compiler can use tail call optimization, then it does not need to stack up the context. So, no stack frames are needed as the resulting executable code uses loops behind the scenes.

主站蜘蛛池模板: 库尔勒市| 彭州市| 遵义县| 登封市| 宝清县| 太谷县| 沁源县| 惠东县| 英吉沙县| 芒康县| 高州市| 岚皋县| 仙居县| 房山区| 鸡东县| 阿荣旗| 和硕县| 宁安市| 柘城县| 洛扎县| 肥东县| 伊吾县| 北票市| 游戏| 鲁山县| 抚宁县| 新邵县| 化德县| 久治县| 长宁县| 云和县| 衡南县| 时尚| 沧州市| 怀安县| 高邮市| 社旗县| 尼木县| 大渡口区| 盈江县| 辽宁省|