尾递归问题 [英] Tail recursion issue

问题描述

我们正在 Scala 中试验并行集合，想检查结果是否有序.为此，我在 REPL 上编写了一个小函数来对我们生成的非常大的列表进行检查:

We were experimenting with parallel collections in Scala and wanted to check whether the result was ordered. For that, I wrote a small function on the REPL to do that check on the very large List we were producing:

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

它因 stackOverflow 失败(这里的问题多么合适！).我期待它是尾部优化的.怎么了?

It fails with a stackOverflow (how appropriate for a question here!). I was expecting it to be tail-optimized. What's wrong?

推荐答案

isOrdered 不是代码中的最后一个调用，&运营商是.试试这个:

isOrdered is not the last call in your code, the & operator is. Try this instead:

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

这篇关于尾递归问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！