As known, Lambda-calculus has no global environment; hence,
implementing recursion looks particularly difficult.
However, C++ does provide a global environment, so it is possible to
implement recursive functions in the traditional way
(notice that the function to be recursively invoked has to be
captured by reference; a
capture by value/copy
would result in the usage of uninitialized variables, with the
consequent segmentation fault).
Fixed point combinators, such as Y, allow working around
this issue.
In pratice, a fixed point combinator "fix" computes the fixed point
of a function G:
fix G = G(fix G)
if G is the
"closed form" of a recursive function,
"fix" computes such a function
Implementing "fix" in C++ based on its definition
"fix(g)=g(fix(g))"
leads to endless recursion,
since C++ passes parameters by value (if the "-Wall" compiler option is
used, g++ even warns about this issue at build time).
This problem can be addressed by
using a lambda expression
to avoid the immediate evaluation of fix(g) (remember how
parameter passing by name can be emulated in C++).
This solution is, however, not a real combinator, since
fix() recursively invokes itself
(hence, it refers a name bound in a non-local environment - in
Lambda-calculus jargon, this function has a free variable).
Implementing a real fixed point combinator (such as Y) is much
more difficult, because
of type checking.
This problem can be worked around using advanced data types,
as done for the omega function
\x.xx
...
...