Composing Functions Leads to StackOverflow

Question

Functional Programming in Scala lists the following example as to how composing functions can lead to a 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

As the book explains, g is a composite function that has 100,000 functions where each one calls the next.

Since foldLeft is tail-recursive, why does this StackOverflowError occur? How, if at all, are tail-recursion and StackOverflow's related?

When (as it's expanded) the second argument (B, A) => B of foldLeft, ((acc, elem) => acc.compose(elem)), doesn't each fold step result in composing only 2 functions?

Answer 1

Since foldLeft is tail-recursive, why does this StackOverflowError occur? How, if at all, are tail-recursion and StackOverflow's related?

When (as it's expanded) the second argument (B, A) => B of foldLeft, ((acc, elem) => acc.compose(elem)), doesn't each fold step result in composing only 2 functions?

Note that the fold itself (i.e. the line val g = ...) doesn't overflow stack. However, g ends up being defined effectively as f(f(...(x))) and therefore you need 100000 stack frames to evaluate g(42) which obviously does overflow.