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

Word count: 3.8kReading time: 13 min

 2021/06/18   Share

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

1.1 基本思想

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

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

这里有两点需要注意：

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

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

1.2 经典运用：

《孙子算经》【鸡兔同笼问题】

今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

二、递推算法

聪明一点的递推算法思想

2.1 基本思想

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

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

执行过程如下：

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

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

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

2.2 经典运用：

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

三、迭代算法(辗转法)

3.1 基本思想

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

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

可分为：

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

3.2 基本步骤

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

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

3.3 经典运用

求平方根问题

四、递归算法

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

4.1 基本思想

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

递归分为两个阶段:

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

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

直接递归：即在函数中调用函数本身。
间接递归：即间接地调用一个函数，如出如func_a调用 func_b, func_b 又调用func_a。间接递归用得不多。

4.1.1 优点

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

4.1.2 缺点

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

4.1.3 注意

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

4.2 经典运用

汉诺塔问题、阶乘问题

五、递归与循环/迭代

5.1 概述

循环是程序控制结构，不是算法，不要混为一谈。

迭代与循环：

迭代中，一般是用循环结构来完成迭代次数的计算。
迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。（用变量的旧值递推出变量的新值）

递归与循环：一切递归问题都可以转化为循环求解。不过有些问题中，递归转换为循环实现，需要自己维护堆栈，比如汉诺塔问题。所有递归都可以改写成循环吗？ （递归转成的循环，应该都是迭代吧？）

因为递归借助函数调用，函数调用本身就是基于调用栈这种结构实现的，只不过这一切都是自动完成的，我们当然也可以用代码手动模拟出来。
更理论一些的解释是这样的，不管是递归还是非递归，这两者都是图灵完备的，既然是图灵完备，那么它们在表达能力上就是等价的，不存在谁不能转为谁的问题。关于图灵完备参考这篇《计算机科学中那些有趣的事实》。
只不过这存在一个难易程度的问题。大家都知道尾递归最容易转为非递归的迭代形式，任何有一定水准的编译器都会有“尾递归优化”功能。本质上是这棵树不是多叉的而是单叉的，单叉的不就退化成链表了嘛，遍历链表当然是简单的，但如果是多叉的话问题就没那么简单了。

递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成循环往往是好的。（例如：求阶乘的递归实现与循环实现。）

要转换成为非递归，两步工作：

第一步，可以自己建立一个堆栈保存这些局部变量，替换系统栈；
第二步，把对递归的调用转变为循环处理就可以了。

5.2 递归算法转为循环(迭代?)求解

递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如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进栈
　　}
}

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

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

5.3 递归与迭代的区别

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

从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)，其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。

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

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，每次在迭代过程中被处理，其结果会作为下次迭代的初始值。

Author：Tenloy

原文链接：https://tenloy.github.io/2021/06/18/several-programming.html

发表日期：2021.06.18 , 9:40 AM

更新日期：2024.05.02 , 6:31 PM

Next Post

(一) 分治算法及减治、变治算法
Previous Post

数据结构与算法概述

