Question

How to perform anonymous recursion in C++

Answer 1

#include <iostream>
#include <functional>

/*
    Anonymous recursion in C++:
    ---------------------------
    Lambdas cannot normally call themselves because they have no name.
    The Y‑combinator pattern solves this by passing the lambda itself
    as an argument, enabling recursion without naming the function.

    We create a higher‑order function `make_recursive` that wraps a lambda
    and gives it a callable "self" parameter.
*/

// Generic Y‑combinator implementation
template <typename F>
auto make_recursive(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

int main() {

    /*
        Example: factorial using anonymous recursion.
        The lambda receives itself as the first parameter (self),
        enabling recursive calls without naming the function.
    */

    auto factorial = make_recursive(
        [](auto self, int n) -> long long {
            if (n <= 1) return 1;
            return n * self(self, n - 1);  // recursive call
        }
    );

    int x = 6;
    long long result = factorial(x);

    std::cout << "factorial(" << x << ") = " << result << "\n";
}


/*
run:

factorial(6) = 720

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>

/*
    ================================
    ANONYMOUS RECURSION
    USING A Y‑COMBINATOR WRAPPER
    ================================

    Problem:
        Lambdas in C++ cannot call themselves directly because
        they have no name.

    Solution:
        Create a wrapper class (Y) that stores a lambda and
        passes itself as the first argument, enabling recursion.

    How it works:
        - The lambda receives "self" as its first parameter.
        - It calls self(...) to recurse.
        - No std::function, no heap allocation, no type erasure.
        - Fully inline and efficient.
*/

// Y‑combinator wrapper class
template <class F>
class Y {
    F f;  // store the lambda
public:
    explicit Y(F&& f) : f(std::forward<F>(f)) {}

    // operator() forwards arguments to the lambda,
    // passing *this as the "self" parameter.
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};

// Helper function to construct Y objects
template <class F>
auto make_recursive(F&& f) {
    return Y<F>(std::forward<F>(f));
}

int main() {

    /*
        Example: factorial using anonymous recursion.

        The lambda signature:
            [](auto self, int n) -> long long

        - "self" is the recursive function.
        - "n" is the argument.
    */

    auto factorial = make_recursive(
        [](auto self, int n) -> long long {
            if (n <= 1) return 1;
            return n * self(n - 1);  // recursive call
        }
    );

    int x = 6;
    long long result = factorial(x);

    std::cout << "factorial(" << x << ") = " << result << "\n";
}


/*
run:

factorial(6) = 720

*/

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>
#include <utility>

/*
    ================================
    MINIMAL ANONYMOUS RECURSION
    USING A TINY Y‑COMBINATOR
    ================================

    This version demonstrates how to perform recursion
    without naming the function.

    The trick:
        - A lambda cannot call itself directly.
        - But it *can* call another lambda passed as a parameter.
        - So we pass the lambda itself as the first argument.
*/

// Minimal Y‑combinator
auto rec = [](auto f) {
    return [f](auto&&... args) {
        // f receives itself (f) as first argument
        return f(f, std::forward<decltype(args)>(args)...);
    };
};

int main() {

    /*
        Example: factorial using anonymous recursion.

        The lambda receives:
            - self: the recursive function
            - n:    the argument

        factorial(n):
            n <= 1 → return 1
            otherwise → n * factorial(n - 1)
    */

    auto factorial = rec(
        [](auto self, int n) -> int {
            if (n <= 1) return 1;
            return n * self(self, n - 1);  // recursive call
        }
    );

    int x = 6;
    int result = factorial(x);

    std::cout << "factorial(" << x << ") = " << result << "\n";
}


/*
run:

factorial(6) = 720

*/

 

70+ SQL courses for beginners and professionals