撰寫功能導致StackOverflow

Question

Functional Programming in Scala列出以下示例以瞭解撰寫功能如何導致StackOverflowError。

scala> val f = (x: Int) => x 
f: Int => Int = <function1> 

scala> val g = List.fill(100000)(f).foldLeft(f)(_ compose _) 
g: Int => Int = <function1> 

scala> g(42) 
java.lang.StackOverflowError 

正如書中解釋說，g是擁有10萬層的功能，其中每一個調用下一​​個複合函數。

由於foldLeft是尾遞歸，爲什麼這個StackOverflowError發生？如果有的話，tail-recursion和StackOverflow的相關性如何？

當（因爲它擴大了）第二個參數(B, A) => B的foldLeft,((acc, elem) => acc.compose(elem))，是否每個摺疊步驟都不會導致只編寫2個函數？

Answer 1

由於foldLeft是尾遞歸，爲什麼這個StackOverflowError發生？如果有的話，tail-recursion和StackOverflow的相關性如何？ （當它被展開時）foldLeft的第二個參數（B，A）=> B，（（acc，elem）=> acc.compose（elem）），並不是每個摺疊步都導致僅組成2個功能？

注意，摺疊本身（即線val g = ...）不會溢出堆棧。然而，g最終被有效地定義爲f(f(...(x)))，因此您需要100000個堆棧幀來評估g(42)，這明顯會發生溢出。

Answer 2

這不是因爲foldLeft或compose本身。這是因爲g(x) = f(f(f(...(x)))。