15-数据结构_递归

深碍√TFBOYSˉ_ 2021-11-29 06:42 326阅读 0赞

递归

# 一, 定义 #

一个函数自己直接或间接调用自己

递归必须满足的两个个条件:  
(1) 递归必须得有一个明确的终止条件  
(2) 该函数所处理的数据规模必须在递减, 即总体上 被调用次数不能增加

# 二, 函数调用 #

引用 《数据结构(C语言版)》严蔚敏 吴伟民 P56 一段话:  
 通常, 当在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需要完成三件事:  
 1, 将所有的实参、返回地址(下条语句的地址)等信息传递给被调用函数保存  
 2, 为被调用函数的局部变量分配存储区  
 3, 将控制转移到被调函数的入口  
 而从被调用函数返回调用函数之前, 系统也要完成三件事:  
 1, 保存被调函数的计算结果  
 2, 释放被调函数的数据区  
 3, 依照被调函数保存的返回地址将控制转移到调用函数  
 当有多个函数构成嵌套调用时, 按照"后调用先返回"的原则, 上述函数之间的信息传递和控制转移必须通过"栈"来实现,即系统将整个程序运行时所需要的数据安排在一个栈中, 每当调用一个函数时,就为它在栈顶分配一个存储区, 每当从一个函数退出时, 就释放它的存储区, 则当前正运行的函数的数据区必在栈顶.

## 1, 调用其他函数 ##

如图

![SouthEast][]

## 2, 调用自己 ##

必须知道什么时候不调自己  
即, 当满足某个条件时, 返回  
如图  
![SouthEast 1][]![SouthEast 2][]

# 三, 递归举例 #

## 1, 求阶乘 ##

(1) 循环实现

(2) 递归实现

#include <stdio.h>
    
    // 递归 实现 阶乘
    long getTactorial_2(int num)
    {
        if (1 == num)
        {
            return 1;
        }
        return num * getTactorial_2( num - 1 );
    }
    
    // 循环 实现 阶乘
    long getTactorial_1(int num)
    {
        int mult = 1;
        for (; num > 0; --num)
        {
            mult *= num;
        }
        return mult;
    }
    
    int main(void)
    {
        int num;
        printf("输入一个整数: ");
        scanf("%d", &num);
        
        printf("%d 的阶乘是: %ld\n", num, getTactorial_1(num));
        printf("%d 的阶乘是: %ld\n", num, getTactorial_2(num));
        
        return 0;
    }

## 2, 求 1 + 2 + 3 + ... + 99 + 100 的和 ##

#include <stdio.h>
    
    int getSum(int num)
    {
        if (1 == num)
        {
            return 1;
        }
        return num + getSum(num - 1);
    }
    
    int main(void)
    {
        int maxNum;
        printf("输入一个整数: ");
        scanf("%d", &maxNum);
    
        printf("1 ~ %d 的和 = %d\n", maxNum, getSum(maxNum) );
    
        return 0;
    }

# 四, 循环 和 递归 优缺点 #

1, 递归  
(1) 优点  
易于理解(针对数据结构中的 树, 图)  
(2) 缺点  
速度慢(参看引用的函数调用过程)  
存储空间大  
2, 循环  
(1) 优点  
速度快  
存储空间小  
(2) 缺点  
不易理解

# 五, 递归的应用 #

树和森林是以递归的方式定义的  
树和图的很多算法都是以递归来是实现的  
很多数学公式都是以递归的方式定义的  
如, 斐波拉契序列 1, 2, 3, 5, 8, 13, ...

[SouthEast]: /images/20211129/a188b123e22c4ac793085f4b6c75b0ef.png
[SouthEast 1]: https://img-blog.csdn.net/20130731203550437?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3VxaW5mZWlfY3M=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20211129/bb86e8a04bea41bfad087aaff4fd2549.png