递归算法
递归算法
更新于 2025/10/16 16:21:06
递归
属性
实现
递归分析
时间复杂度
空间复杂度
示例
递归
某些计算机编程语言允许模块或函数调用自身。这种技术称为递归。在递归中，函数 α 可以直接调用自身，也可以调用函数 β，而后者又调用原始函数 α。函数 α 称为递归函数。
示例 − 一个调用自身的函数。
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}
示例 − 一个函数调用另一个函数，而该函数又再次调用它。
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}
属性
递归函数可以像循环一样无限运行。为了避免递归函数无限运行，递归函数必须具备两个属性：−
基本条件 − 必须至少有一个基本条件或条件，当满足此条件时，函数将停止递归调用。
渐进式方法 − 递归调用应以这样的方式进行：每次递归调用都更接近基本条件。
实现
许多编程语言通过堆栈实现递归。通常，每当一个函数（调用者）调用另一个函数（被调用者）或自身作为被调用者时，调用者函数都会将执行控制权转移给被调用者。此转移过程可能还涉及将一些数据从调用者传递给被调用者。
这意味着，调用者函数必须暂时暂停执行，并在执行控制权从被调用者函数返回后恢复执行。此时，调用者函数需要从暂停执行的位置准确开始执行。它还需要与之前处理的数据值完全相同。为此，会为调用函数创建一个激活记录（或称堆栈框架）。
此激活记录保存了局部变量、形式参数、返回地址以及传递给调用函数的所有信息。
递归分析
有人可能会质疑为什么要使用递归，因为同样的任务可以用迭代完成。第一个原因是，递归使程序更具可读性，而且由于最新的增强型 CPU 系统，递归比迭代更高效。
时间复杂度
对于迭代，我们采用迭代次数来计算时间复杂度。同样，在递归的情况下，假设所有变量保持不变，我们尝试计算递归调用的次数。对函数的一次调用为 (1)，因此递归调用的次数 (n) 使得递归函数为 (n)。
空间复杂度
空间复杂度是指模块执行所需的额外空间量。在迭代的情况下，编译器几乎不需要任何额外空间。编译器会不断更新迭代中使用的变量值。但在递归的情况下，系统需要在每次递归调用时存储激活记录。因此，递归函数的空间复杂度可能高于迭代函数。
示例
以下是各种编程语言中递归的实现−
C
C++
Java
Python
// 递归数据结构的 C 程序
#include
int factorial(int n) {
// 基本情况：0 的阶乘为 1
if (n == 0)
return 1;
// 递归情况：将 n 与 (n-1) 的阶乘相乘
return n * factorial(n - 1);
}
int main() {
// case 1
int number = 6;
printf("Number is: %d
" , 6);
//case 2
if (number < 0) {
printf("Error: Factorial is undefined for negative numbers.
");
return 1;
}
int result = factorial(number);
//print the output
printf("Factorial of %d is: %d
", number, result);
return 0;
}
输出
Number is: 6
Factorial of 6 is: 720
// 递归数据结构的 CPP 程序
#include
int factorial(int n) {
// 基本情况：0 的阶乘为 1
if (n == 0)
return 1;
// 递归情况：将 n 与 (n-1) 的阶乘相乘
return n * factorial(n - 1);
}
int main() {
// case 1
int number = 6;
std::cout<<"Number is: "< "; //case 2 if (number < 0) { std::cout << "Error: Factorial is undefined for negative numbers. "; return 1; } int result = factorial(number); //print the output std::cout << "Factorial of " << number << " is: " << result << std::endl; return 0; } 输出 Number is: 6 Factorial of 6 is: 720 // 递归数据结构的 Java 程序 import java.util.Scanner; public class Main { public static int factorial(int n) { // 基本情况：0 的阶乘为 1 if (n == 0) return 1; // 递归情况：将 n 与 (n-1) 的阶乘相乘 return n * factorial(n - 1); } public static void main(String[] args) { //Case 1 int number = 6; System.out.println("Number is: " + number); //Case 2 if (number < 0) { System.out.println("Error: Factorial is undefined for negative numbers."); System.exit(1); } int result = factorial(number); //print the output System.out.println("Factorial of " + number + " is: " + result); } } 输出 Number is: 6 Factorial of 6 is: 720 # 递归数据结构的 Python 程序 def factorial(n): # 基本情况：0 的阶乘为 1 if n == 0: return 1 # 递归情况：将 n 与 (n-1) 的阶乘相乘 return n * factorial(n - 1) #Case 1: number = 6; print("Number is: ", number); #Case 2: if number < 0: print("Error: Factorial is undefined for negative numbers.") else: result = factorial(number) # print the output print("Factorial of", number, "is: ", result) 输出 Number is: 6 Factorial of 6 is: 720