constexpr with Recursive Functions

Yes, you can use both constexpr and consteval with recursive functions. This is a powerful feature that allows you to perform complex compile-time computations. Let's explore this with some examples:

Basic Recursive constexpr Function

Here's a classic example of a recursive factorial function using constexpr. This function will be evaluated at compile-time when used in a constant expression.

1#include <iostream>
2
3constexpr int factorial(int n) {
4  if (n <= 1) return 1;
5  return n * factorial(n - 1);
6}
7
8int main() {
9  constexpr int result = factorial(5);
10  std::cout << "5! = " << result;
11}

15! = 120

Recursive consteval Function

You can also use consteval to ensure the function is always evaluated at compile-time:

1#include <iostream>
2
3consteval int fibonacci(int n) {
4  if (n <= 1) return n;
5  return fibonacci(n - 1) + fibonacci(n - 2);
6}
7
8int main() {
9  constexpr int result = fibonacci(10);
10  std::cout << "10th Fibonacci number: "
11    << result << '\n';
12}

110th Fibonacci number: 55

Compile-Time Limitations

While you can use recursion in constexpr and consteval functions, be aware of compiler limitations. Most compilers have a limit on the depth of constexpr recursion:

This might result in a compiler error or warning about exceeding recursion limits.

1constexpr long long very_deep_recursion(int n) {
2  if (n == 0) return 0;
3  return 1 + very_deep_recursion(n - 1);
4}
5
6int main() {
7  // Might exceed limits
8  constexpr int result = very_deep_recursion(1000); 
9}

1error: expression did not evaluate to a constant
2note: failure was caused by evaluation exceeding call depth limit of 512

Practical Use Case - Compile-Time String Hashing

Here's a more practical example using recursion to compute a string hash at compile-time:

This recursive function computes the FNV-1a hash of a string at compile-time, which could be useful for switch statements or other compile-time decisions based on strings.

1#include <iostream>
2#include <string_view>
3
4constexpr uint32_t fnv1a_32(
5  std::string_view sv, size_t idx = 0) {
6  constexpr uint32_t FNV_offset_basis = 2166136261U;
7  constexpr uint32_t FNV_prime = 16777619U;
8
9  return idx == sv.size() ? FNV_offset_basis
10    : (fnv1a_32(sv, idx + 1) ^ sv[idx]) * FNV_prime;
11}
12
13int main() {
14  constexpr auto hash = fnv1a_32("Hello, World!");
15  std::cout << "Hash of 'Hello, World!': " << hash;
16}

1Hash of 'Hello, World!': 3644920852

Remember, when using recursion in constexpr or consteval functions, ensure that there's a clear base case to prevent infinite recursion. Also, be mindful of the potential for long compilation times with complex recursive computations.

Despite these considerations, recursive constexpr and consteval functions are powerful tools for compile-time metaprogramming in C++.