函数递归是指一个函数在其定义中直接或间接地调用自身的编程技巧。递归通常包含两个关键部分:基本情况(Base Case)和递归情况(Recursive Case)。基本情况是递归终止的条件,避免无限递归;递归情况则是函数调用自身以解决规模更小的子问题。
比如计算阶乘。一个非负整数 n 的阶乘(表示为 n!)定义为:
当 n = 0 或 n = 1 时,n! = 1(基本情况)
当 n > 1 时,n! = n * (n – 1)!(递归情况)
用C++来实现这一过程:
// 递归计算阶乘
int factorial(int n)
{
// 基本情况
if (n == 0 || n == 1)
return 1;
// 递归情况
return n * factorial(n – 1);
}
在上述代码中,factorial 函数直接调用自身来计算阶乘。当 n 为 0 或 1 时,函数返回 1,递归终止;否则,函数返回 n 乘以 (n – 1) 的阶乘。
递归是一种强大的编程技巧,但在使用时需要注意递归深度,避免栈溢出的问题。对于一些复杂的递归问题,也可以考虑使用迭代方法来替代递归,以提高性能。