[andreyf]

Very nice, this seems like it might be my first successful attempt at understanding the importance of the Y combinator. Question:

As an example of the power of this approach, this caching turns the naive, exponential implementation of Fibonacci into the optimized, linear-time version

What role does the YC play in this? Is it not simply due to memoization? Does the Y-combinator version grow the stack?

[fadmmatt]

The role the YC plays in this case is hiding the memoization.

The memoizing Y combinator is the same as the Y combinator, except it doesn't re-compute inputs it's already seen.

Writing recursive functions in "Y-combinator style" is a way to expose internal recursive call sites to external inspection and manipulation.

The Y combinator version still grows the stack.