C++ 递归

递归

递归是一种让函数调用自身的技术。

这项技术提供了一种将复杂问题分解为更容易解决的简单问题的方法。

递归可能有点难以理解。弄清楚它如何工作的最佳方法是动手实验。

递归示例

将两个数相加很容易，但将一系列数字相加则更复杂。

在下面的示例中，使用递归将一系列数字相加，将其分解为两个数相加的简单任务：

实例

int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

int main() {
  int result = sum(10);
  cout << result;
  return 0;
}

亲自试一试

示例解释

当调用 sum() 函数时，它将参数 k 与所有小于 k 的数字之和相加，并返回结果。当 k 变为 0 时，函数只返回 0。运行时，程序遵循以下步骤：

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

由于当 k 为 0 时函数不再调用自身，程序在此停止并返回结果。

倒计时

此例演示如何使用递归创建一个倒计时函数：

实例

void countdown(int n) {
  if (n > 0) {
    cout << n << " ";
    countdown(n - 1);
  }
}

int main() {
  countdown(5);
}

亲自试一试

该函数用 n - 1 调用自身，直到 n 变为 0。

数字的阶乘

此例使用递归函数计算 5 的阶乘：

int factorial(int n) {
  if (n > 1) {
    return n * factorial(n - 1);
  } else {
    return 1;
  }
}

int main() {
  cout << "5 的阶乘是 " << factorial(5);
  return 0;
}

亲自试一试

阶乘是指将一个数字乘以它下面的每个数字，直到 1（例如，5 的阶乘是：5 * 4 * 3 * 2 * 1 = 120）。