数据结构 - 递归基础知识

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

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

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 program for Recursion Data Structure
#include <stdio.h>
int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0)
        return 1;
    // Recursive case: multiply n with factorial of (n-1)
    return n * factorial(n - 1);
}
int main() {
    // case 1
    int number = 6;
    printf("Number is: %d\n" , 6);
    //case 2
    if (number < 0) {
        printf("Error: Factorial is undefined for negative numbers.\n");
        return 1;
    } 
    int result = factorial(number);
    //print the output
    printf("Factorial of %d is: %d\n", number, result);
    return 0;
}

Number is: 6
Factorial of 6 is: 720

// CPP program for Recursion Data Structure
#include <iostream>
int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0)
        return 1;  
    // Recursive case: multiply n with factorial of (n-1)
    return n * factorial(n - 1);
}
int main() {
    // case 1
    int number = 6;
    std::cout<<"Number is: "<<number<<"\n";
    //case 2
    if (number < 0) {
        std::cout << "Error: Factorial is undefined for negative numbers.\n";
        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 program for Recursion Data Structure
import java.util.Scanner;
public class Main {
    public static int factorial(int n) {
        // Base case: factorial of 0 is 1
        if (n == 0)
            return 1;
        // Recursive case: multiply n with factorial of (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 program for Recursion Data Structure
def factorial(n):
    #Base Case: factorial of 0 is 1
    if n == 0:
        return 1
    # Recursive case: multiply n with factorial of (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