递归算法

递归

某些计算机编程语言允许模块或函数调用自身。这种技术称为递归。在递归中，函数 α 可以直接调用自身，也可以调用函数 β，而后者又调用原始函数 α。函数 α 称为递归函数。

示例 − 一个调用自身的函数。

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 程序
#include <stdio.h>
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 <iostream>
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: "<<number<<"
";
    //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