Passing recursive C++ lambdas as function pointers

In modern C++, as in many popular languages, you can create ‘lambdas’. Effectively, they are potentially anonymous function instances that you can create on the fly as you are programming, possibly inside another function. The following is a simple example.

auto return1 = [](int n) -> int { return 1; };

What about recursive functions? At first I thought you could do…

auto fact = [](int n) -> int {
 if (n == 0) {
   return 1;
 } else {
  return n * fact(n - 1);
 }
};

Sadly it fails. What seems to be happening is that while it recognizes the variable ‘fact’ within the definition of ‘fact’, it cannot use it without knowing its type. So you should specify the type of the ‘fact’ right away. The following will work:

std::function<int(int)> fact = [](int n) -> int {
  if (n == 0) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
};

But using std::function templates may add complexity. For example, what if you have a function that takes a function as a parameter without using std::function, such as…

void print(int(*f)(int)) {
  for(int k = 1; k < 10; ++k) {
   std::cout << "Factorial of " << k << " is " << f(k) << std::endl;
  }
}

Then you would want to call print(fact), but it will not work directly. It may complain like so:

No known conversion from 'std::function' to 'int (*)(int)

So let us avoid the std::function as much as possible:

int (*factorial)(int) = [](int n) -> int {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
};

And then everything works out fine:

    print(factorial); // OK

Let me finish with a word of caution: functional programming is sophisticated, but it has downsides. One potential downside is performance. Let us consider this conventional code:

int factorialc(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorialc(n - 1);
  }
}
int functionc() {
  return factorialc(10);
}

Most compilers should produce highly optimized code in such a scenario. In fact, it is likely that the returned value of ‘functionc’ gets computed a compile time. The alternative using lambdas might look as follows:

int (*lfactorial)(int) = [](int n) -> int {
  if (n == 0) {
    return 1;
  } else {
    return n * lfactorial(n - 1);
  }
};

int functionl() {
  return lfactorial(10);
}

Though the results will depend on your system, I would expect far less efficient code in general.

Thus when programming in C++,  if you use lambdas in performance critical code, run benchmarks or disassemble your function to make sure that you have, indeed, zero-cost abstraction.

My source code is available.

Credit: Thanks to Ca Yi, Yagiz Nizipli and many X users for informing this post.

Further reading: Recursive lambdas from C++14 to C++23

Daniel Lemire, "Passing recursive C++ lambdas as function pointers," in Daniel Lemire's blog, March 22, 2024.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

5 thoughts on “Passing recursive C++ lambdas as function pointers”

  1. Before C++23 and explicit this, you may pass lambda to itself as a templated parameter to avoid using function pointers.
    Example:
    auto factorial = [](uint n){
    auto f = [](auto f, uint n){
    if (n == 0)
    return 1;
    else
    return n * f(f, n);
    };
    return f(f, n);
    };

  2. Pasting the factorial code on Godbolt does produce the desired result. The recursion in factorialc gets eliminated at O2 using gcc 13.2. Under O3, functionc returns a precomputed value.

    None of these optimizations are made for lambdas.

    Also, factorialc has a typo: it should call factorialc in the recursion, not factorial.

    1. Thanks for pointing out the typo.

      > None of these optimizations are made for lambdas.

      I don’t think anything prevents the compiler from optimizing lambdas as well, in principle.

Leave a Reply

Your email address will not be published.

You may subscribe to this blog by email.