1. 递归函数简介

递归是一种将复杂问题分解为同类型的较小问题的编程方法。在C++中，递归不仅继承了传统的递归特性，还能够结合现代C++特性实现更优雅的解决方案。

2. C++递归特性

• 模板递归
• 类型递归
• 可变参数模板递归
• 智能指针与递归
• Lambda表达式与递归

3. 现代C++递归示例

3.1 模板元编程递归

 template
 struct Factorial {
     static const unsigned value = N * Factorial::value;
 };
 
 template<>
 struct Factorial<0> {
     static const unsigned value = 1;
 };

3.2 可变参数模板递归

 template
 T sum(T t) {
     return t;
 }
 
 template
 T sum(T first, Args... args) {
     return first + sum(args...);
 }

3.3 智能指针实现二叉树

 template
 struct TreeNode {
     T value;
     std::shared_ptr<TreeNode> left;
     std::shared_ptr<TreeNode> right;
     
     void traverseInOrder() {
         if (left) left->traverseInOrder();
         std::cout << value << if right right->traverseInOrder();
     }
 };

3.4 Lambda递归

 #include 
 
 std::function fibonacci = [&fibonacci](int n) {
     if (n <= 1) return n;
     return fibonacci(n - 1) + fibonacci(n - 2);
 };

3.5 C++17折叠表达式递归

 template
 auto sum_fold(Args... args) {
     return (... + args);
 }
 
 template
 auto multiply_fold(Args... args) {
     return (... * args);
 }

3.6 C++20协程与递归

 #include 
 #include 
 
 struct RecursiveGenerator {
     struct promise_type;
     using handle_type = std::coroutine_handle;
     
     struct promise_type {
         int current_value;
         auto get_return_object() { return RecursiveGenerator{handle_type::from_promise(*this)}; }
         auto initial_suspend() { return std::suspend_always{}; }
         auto final_suspend() noexcept { return std::suspend_always{}; }
         void return_void() {}
         void unhandled_exception() { std::terminate(); }
         auto yield_value(int value) {
             current_value = value;
             return std::suspend_always{};
         }
     };
     
     handle_type h;
     RecursiveGenerator(handle_type h) : h(h) {}
     ~RecursiveGenerator() { h.destroy(); }
     
     int current_value() { return h.promise().current_value; }
     bool move_next() { return h.resume(); }
 };
 
 RecursiveGenerator fibonacci_coroutine(int n) {
     if (n <= 1) {
         co_yield n;
         co_return;
     }
     
     int a = 0, b = 1;
     co_yield a;
     co_yield b;
     
     for(int i = 2; i <= n; ++i) {
         int next = a + b;
         co_yield next;
         a = b;
         b = next;
     }
 }

3.7 C++20 Concepts与递归

 #include 
 
 template
 concept Numerical = std::integral || std::floating_point;
 
 template
 T safe_recursive_sum(T value) {
     if (value <= 1)
         return value;
     return value + safe_recursive_sum(value - 1);
 }

4. 高级应用场景

1. 编译期计算
2. 类型萃取
3. 元编程
4. 复杂数据结构操作

4.1 编译期递归计算

 template
 constexpr int fibonacci() {
     if constexpr (N <= 1)
         return N;
     else
         return fibonacci() + fibonacci();
 }

5. 性能优化技巧

5.1 使用std::optional避免异常

std::optional safe_recursive_function(int n) {
    if (n < 0) return std::nullopt;
    if (n <= 1) return n;
    
    auto prev1 = safe_recursive_function(n - 1);
    auto prev2 = safe_recursive_function(n - 2);
    
    if (!prev1 || !prev2) return std::nullopt;
    return *prev1 + *prev2;
}

5.2 移动语义优化

template
std::vector merge_sort(std::vector&& vec) {
    if (vec.size() <= 1) return std::move(vec);
    
    auto mid = vec.size() / 2;
    auto left = std::vector(vec.begin(), vec.begin() + mid);
    auto right = std::vector(vec.begin() + mid, vec.end());
    
    return merge(merge_sort(std::move(left)), 
                merge_sort(std::move(right)));
}

6. 最佳实践

1. 使用现代C++特性
2. 注重异常安全
3. 考虑移动语义
4. 利用编译期优化
5. 合理使用智能指针

7. 调试技巧

1. 使用静态分析工具
2. 利用模板调试技术
3. 编译期断言

8. 注意事项

1. 模板递归深度限制
2. 内存管理
3. 异常处理
4. 性能考虑

总结

现代C++中的递归不仅仅是简单的函数自调用，还包含了丰富的模板元编程、智能指针管理、移动语义等特性。合理运用这些特性，可以写出更安全、更高效的递归代码。掌握C++递归技术对于编写高质量的代码至关重要。