递归是一种函数调用自身的编程技术，适用于分而治之的问题。在 c++++ 中，递归函数定义为：returntype functionname(parameters)，需有明确的基线情况（终止条件）和递归调用（更新参数后调用自身）。阶乘计算是递归的经典案例，其代码如下：`cpplong factorial(int n) { if (n == 0) {return 1;} else {return n * factorial(n-1);}}

递归在 C++ 中的应用

简介

递归是一种强大的编程技术，它允许函数调用自己。它通常用于解决具有分而治之性质的问题，即问题可以分解成较小的子问题，这些子问题可以递归解决。

语法

在 C++ 中，递归函数使用如下语法定义：

returnType functionName(parameters) {
  // 基线情况：当递归终止时要满足的条件
  if (base_case) {
    return result;
  }

  // 递归调用：函数调用自己，传入更新后的参数
  return functionName(updated_parameters);
}

实战案例：阶乘

求一个非负整数的阶乘是递归的经典例子。阶乘定义为：

factorial(n) = 1,                   if n = 0
              = n * factorial(n-1), if n > 0

以下代码实现了一个递归函数来计算阶乘：

#include <iostream>

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

int main() {
  int n;
  std::cout << "Enter a non-negative integer: ";
  std::cin >> n;

  std::cout << "The factorial of " << n << " is: " << factorial(n) << std::endl;

  return 0;
}

其他应用

递归还可用于解决各种问题，包括：

• 遍历树和图
• 快速排序和归并排序
• 动态规划
• 回溯法

提示

• 确保递归函数有明确的基线情况，以防止无限递归。
• 谨慎使用递归，因为它可能导致栈溢出。
• 对于有大量子问题的递归问题，可以使用备忘录或尾递归优化来提高效率。