I have a recursive function (in C#) that I need to call about 800 million times; this would obviously normally result in a stack overflow after about the 900th call. I've kicked this out to multiple loops, but the recursive pattern is just so much easier, and cleaner to maintain.
I'm looking at implementing the recursive function using a y-combinator, as from what I'm reading and seen, that should solve the stack overflow problem, and fix the multiple nested loops.
Does anyone have experience using the y-combinator? Will I still be stuck in a stack overflow?
Take the simple example of a factorial. A factorial on most numbers bigger than like 5,000 will cause a stack overflow. If I used a y-combinator properly in that scenario, would it fix the stack overflow?
It doesn't seem trivial to implement, so I want to confirm it before I spend the development effort/resources implementing and learning the y-combinator.
No, using the Y-combinator will not help your situation. If you need to do something 800 million times, you can either (a) recurse, or (b) loop (or I suppose (c) write 800 million calls to your function). Since the Y-combinator doesn't loop, it must therefore recurse.
A loop is what you're looking for, unless you're using a runtime environment that offers proper tail recursion (such as Scheme).
Having said that, implementing the Y-combinator from scratch in the language of your choice is an excellent exercise.