搜索
Tenloy's Blog

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

Word count: 3.3kReading time: 11 min
2021/06/18 Share

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

1.1 基本思想

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

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

这里有两点需要注意：

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

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

1.2 经典运用：

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

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

二、递推算法

聪明一点的递推算法思想

2.1 基本思想

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

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

执行过程如下：

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

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

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

2.2 经典运用：

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

三、迭代算法(辗转法)

3.1 基本思想

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

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

可分为：

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

3.2 基本步骤

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

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

3.3 经典运用

求平方根问题

四、递归算法

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

4.1 基本思想

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

递归分为两个阶段:

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

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

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

4.1.1 优点

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

4.1.2 缺点

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

4.1.3 注意

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

4.2 经典运用

汉诺塔问题、阶乘问题

五、对比

5.1 递归与迭代的区别、联系

img

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

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

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

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

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

1
2
3
4
5
6
7
8
9
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，每次在迭代过程中被处理，其结果会作为下次迭代的初始值

5.2 递归与循环

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

迭代与循环：迭代中，一般是用循环结构来完成迭代次数的计算。

递归与循环：一切递归问题都可以转化为循环求解。不过有些问题中，递归转换为循环实现，需要自己维护堆栈，比如汉诺塔问题。

5.2.1 递归算法转为循环求解

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

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

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

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

1. 直接转换法

直接转换法通常用来消除 尾递归和 单向递归，将递归结构用循环结构来替代。

尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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. 间接转换法

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

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

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

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

Author：Tenloy

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

发表日期：2021.06.18 , 9:40 AM

更新日期：2024.04.07 , 8:02 PM

版权声明：本文采用Crative Commons 4.0 许可协议进行许可

CATALOG
  1. 一、穷举(枚举、暴力、强力)算法
    1. 1.1 基本思想
    2. 1.2 经典运用：
  2. 二、递推算法
    1. 2.1 基本思想
    2. 2.2 经典运用：
  3. 三、迭代算法(辗转法)
    1. 3.1 基本思想
    2. 3.2 基本步骤
    3. 3.3 经典运用
  4. 四、递归算法
    1. 4.1 基本思想
      1. 4.1.1 优点
      2. 4.1.2 缺点
      3. 4.1.3 注意
    2. 4.2 经典运用
  5. 五、对比
    1. 5.1 递归与迭代的区别、联系
    2. 5.2 递归与循环
      1. 5.2.1 递归算法转为循环求解
        1. 1. 直接转换法
        2. 2. 间接转换法
数据结构与算法 计算机组成原理 计算机网络 汇编语言 数据的存储与传输 操作系统 互联网标准RFC 编译链接与装载 iOS 架构与设计模式 图形处理与渲染 软件工程 音视频处理 DSL Swift Git Web
Total : 75
搜索
2022
2021
2020
AutoreleasePool GCD hexo ISA Microarch Soc CLI Shell ARM64 多线程 Docker DSL 协程 Fiber dp RunLoop SwiftUI Swift-Syntax LagMonitor CrashMonitor Log AFN