我已经阅读过帖子，提到Scala有一个尾递归优化。
但是这个怎么样：
def f(i: Int): List[Int] = { if (i == 0) Nil else i :: f(i - 1) // Is there any optimizations? }第5行不是尾递归。
Scala是否对它有某种优化？ 或者它可能消耗更多的堆栈空间，然后它的命令版本？
I have read posts mentioned that Scala has a tail recursion optimization.
But how about this one:
def f(i: Int): List[Int] = { if (i == 0) Nil else i :: f(i - 1) // Is there any optimizations? }The line 5 is not a tail recursion.
Does Scala has some kind of optimizations on it? Or it may consume much more stack spaces then its imperative version?
最满意答案
就目前来看，这段代码将在一个单独的栈帧中计算每个递归。 如果i足够大，那么你的内存就会耗尽。
scala> f(10000) java.lang.StackOverflowError at .f(<console>:15) at .f(<console>:15) at .f(<console>:15)所以编译器可以做的很少，以帮助提高效率。
你可以防止i太大（如果这符合你的要求，但可能不是很好），或者使它尾部递归，以便可以在恒定的堆栈空间中计算。
举个例子。
scala> @tailrec def f(i: Int, x: List[Int] = List()): List[Int] = { | if (i == 0) | x.reverse | else | f(i - 1, i :: x) | } f: (i: Int, x: List[Int])List[Int] scala> f(10) res10: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)请注意，返回之前列表（ x.reverse ）的反转是0(n) （复杂度），但只有在明显需要相反顺序时才需要。
As it currently stands this code will compute each recursion in a separate stack frame. If i is sufficiently large then you run out of memory.
scala> f(10000) java.lang.StackOverflowError at .f(<console>:15) at .f(<console>:15) at .f(<console>:15)So the compiler can do little to help make this more efficient.
You can either guard against i being too large (if that works for your requirement but is not very nice perhaps), or else make it tail recursive so it can be computed in constant stack space.
As an example.
scala> @tailrec def f(i: Int, x: List[Int] = List()): List[Int] = { | if (i == 0) | x.reverse | else | f(i - 1, i :: x) | } f: (i: Int, x: List[Int])List[Int] scala> f(10) res10: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)Note that the reversal of the list (x.reverse) before returning it is 0(n) (complexity) but only necessary if you need it in reverse order obviously.
更多推荐
发布评论