穷举算法、递推算法、迭代算法(辗转法)、递归算法

不念不忘少年蓝@ 2023-10-14 14:52 62阅读 0赞

#### 穷举(枚举、暴力、强力)算法 ####

##### \#\# 基本思想 #####

在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。穷举算法效率并不高，但是适应于一些没有明显规律可循的场合。

使用穷举法思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。

这里有两点需要注意：

1.  解空间的划定必须保证覆盖问题的全部解
2.  是解空间集合及问题的解集一定是离散的集合，也就是说集合中的元素是可列的、有限的。

穷举法用时间上的牺牲换来了解的全面性保证，因此穷举法的优势在于确保得到问题的全部解，而瓶颈在于运算效率十分低下。但是穷举法算法思想简单，易于实现，在解决一些规模不是很大的问题，使用穷举法不失为一种很好地选择，而无须太在意是够还有更快的算法。

##### \#\# 经典运用： #####

《孙子算经》【鸡兔同笼问题】  
今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

#### \# 递推算法 ####

> 聪明一点的递推算法思想

##### \#\# 基本思想 #####

递推(`recurrence`)算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。`从已知到未知，从小到大`，这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用 `循环`可以实现。

*  顺推法：从已知条件出发，逐步推算出要解决问题的方法
 *  逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件。

执行过程如下：

1.  根据已知结果和关系，求解中间结果。
2.  判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。

【注意】递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有明确的计算公式可以遵循，因此可以采用递推算法来实现。

典型代表fibonacci数列递推求法（后一项等于前两项之和）`f(n) = f(n-1) + f(n-2)`

##### \#\# 经典运用： #####

算盘书、斐波那契数列(兔子繁殖)（顺推法）、银行存款（逆推法）

#### \# 迭代算法(辗转法) ####

##### \#\# 基本思想 #####

迭代：在计算过程中，不断用变量的旧值 `递推`出变量的新值。是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而`每一次迭代得到的结果会作为下一次迭代的初始值`。

*  解决问题时总是重复利用一段程序(可以是几行代码，也可以是一个函数)
 *  一直在更新这个变量值，迭代的含义
 *  从一个 `初始估计`出发寻找 `一系列近似解`来解决问题的数学过程

可分为：

*  精确迭代
 *  近似迭代：二分法和牛顿迭代法

##### \#\# 基本步骤 #####

用迭代算法解决问题时，需要做好3个方面的工作

1.  确定迭代变量：直接或间接地不断由旧值递推出新值的变量
2.  建立迭代关系式：新值与旧值的公式或关系。（解决迭代问题的关系）
3.  对迭代过程进行控制：确定迭代次数和迭代结束条件
    
     *  所需的迭代次数是个确定值，可以计算出来：可以构建一个固定次数的循环来实现对迭代过程的控制；
     *  所需的迭代次数无法确定：需要进一步分析出用来结束迭代过程的条件。

##### \#\# 经典运用： #####

求平方根问题

#### \# 递归算法 ####

> 充分利用自己的递归算法思想

##### \#\# 基本思想 #####

*  **递归函数**：一个函数在它的函数体内调用它自身的函数调用方式，这种函数也称为`递归函数`。在递归函数中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。
 *  **递归函数的两个要素**：边界条件、递归方程
 *  **递归算法**：一种直接或间接地调用原算法本身的一种算法。往往可以简化代码编写，提高程序的可读性。但是，不合适的递归会导致程序的执行效率变低。
    
     *  递归过程一般通过函数或子过程实现；
     *  递归算法在函数或子过程的内部，直接或间接调用自己的算法
     *  递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解

递归分为两个阶段:

1.  递推：把复杂的问题的求解推到比原问题简单一些的问题的求解;
2.  回归：当获得最简单的情况后, 逐步返回, 依次得到复杂的解.

函数的递归调用分两种情况：直接递归和间接递归。

*  直接递归：即在函数中调用函数本身。
 *  间接递归：即间接地调用一个函数，如出如func\_a调 用 func\_b, func\_b 又调用func\_a。间接递归用得不多。

###### 优点： ######

代码简洁、可读性好（这一点，对于初学者可能会反对）。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。

###### 缺点： ######

由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能会造成栈溢出

###### 注意： ######

*  `必须有一个明确的递归结束条件(递归出口)`
 *  `如果递归次数过多，容易造成栈溢出。`

##### \#\# 经典运用： #####

汉诺塔问题、阶乘问题

#### \# 迭代与递归的区别、联系 ####

![format_png][]

从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。

但从算法结构来说，`递归声明的结构并不总能够转换为迭代结构`，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。

这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，`一个极典型的例子类似于链表`，使用递归定义及其简单，但对于内存定义(数组方式)，其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说，`所有的迭代可以转换为递归，但递归不一定可以转换为迭代。`

**采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛（有确定的(或有限的)极限）时，才可采用递归算法，否则，就不能使用递归算法。**

###### 递归中一定有迭代、递归不一定能转为迭代举例 —— 链表定义 ######

ElemSN* CreatLink3(int data[], int n) //递归法创建链表
    {
        ElemSN *p = NULL;
        if(n==0) return NULL;
        p = (ElemSN *)malloc(sizeof(ElemSN));
        p->data = data[n-1];
        p->next = CreatLink3(data, n-1);
        return P;
    }

递归中一定有迭代(递归函数的传入参数每次都会被递归函数处理，并赋予新值)。比如这个递归，虽然不能转换成迭代结构，但其中仍然有迭代，迭代变量为n，每次在迭代过程中被处理，其结果会作为下次迭代的初始值

##### \#\# 循环 #####

循环是程序控制结构，不是算法，不要混为一谈。  
**迭代与循环**：迭代中，一般是用循环结构来完成迭代次数的计算。  
**递归与循环**：一切递归问题都可以转化为循环求解。不过有些问题中，递归转换为循环实现，需要自己维护堆栈，比如[汉诺塔问题][Link 1]

###### \#\#\# 递归算法转为循环求解 ######

递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种情况：

*  一种是简单递归问题，可以直接求值，不需要回溯。使用一些变量保存中间结果，称为`直接转换法`；比如`尾递归`(最后一句话进行递归)、`单向递归`(函数中只有一个递归调用地方)
 *  另一种是复杂递归问题，不能直接求值，需要回溯。需要使用栈保存中间结果加以实现，称为`间接转换法`。

使用非递归方式实现递归问题的算法程序，不仅可以节省存储空间，而且可以极大地提高算法程序的执行效率。下面分别讨论这两种方法。

###### 1. 直接转换法 ######

直接转换法通常用来消除 `尾递归`和 `单向递归`，将递归结构用循环结构来替代。  
`尾递归`是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：

long fact(int n)
    {
    　　if(n==0) return 1;
    　　else return n*fact(n-1);
    }

当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：

long fact(int n)
    {
    　　int s=0;
    　　for(int i=1; i<=n;i++)
    　　s=s*i; //用s保存中间结果
    　　return s;
    }

`单向递归`是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：

int f(int n)
    {
    　　if(n == 1 || n ==0) return 1;
    　　else return f(n-1)+f(n-2);
    }

对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果，非递归函数如下：

int f(int n)
    {
    　　int i, s;
    　　int s1=1, s2=1;
    　　for(i=3; i<=n; ++i){
          s=s1+s2;
          s2=s1;// 保存f(n-2)的值
          s1=s;//保存f(n-1)的值
    　　}
    　　return s;
    }

###### 2. 间接转换法 ######

该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：

将初始状态s0进栈
    while(栈不为空){
    　　退栈，将栈顶元素赋给s;
    　　if(s是要找的结果) 返回;
    　　else{
    　　   寻找到s的相关状态s1;
    　　   将s1进栈
    　　}
    }

间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现(参考数据结构中树的递归、非递归(迭代)遍历)、图的深度优先遍历算法的非递归实现等等。

尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。**`编译器会自动把尾递归优化为循环`**

[format_png]: https://img-blog.csdnimg.cn/img_convert/27c5d059fc1227df207446622a4a2022.webp?x-oss-process=image/format,png
[Link 1]: https://links.jianshu.com/go?to=https%3A%2F%2Fblog.csdn.net%2Fliuqiaoyu080512%2Farticle%2Fdetails%2F8453006