【数据结构必备基本知识】递归与迭代的联系、区别与优缺点对比详解

╰+哭是因爲堅強的太久メ 2021-09-16 16:18 124阅读 0赞

在后续的数据结构操作中，可能我们经常会用到递归或者是迭代，这会大大降低我们的代码量，并且能够解决一些其他方法很难解决的问题。以上一篇[二叉树的遍历][Link 1]为例，通过递归算法，只用几行就可以遍历整个二叉树，递归的作用可想而知。

那么，什么是递归，什么是迭代，他们二者之间有什么联系，有什么区别，各自的优缺点是什么呢？接下来给大家详细讲解一下。

# 一、递归（ recursion） #

## 1、定义 ##

首先，**递归是一种计算机算法，它是程序调用自身的编程技巧，**在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

## 2、必要条件 ##

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

## 3、优点 ##

1.可以将大问题转化为小问题，减少代码量。

2.可以去掉不断重复的代码，使代码精简，提升可读性。

## 4、缺点 ##

递归调用浪费空间，递归太深还容易造成堆栈的溢出。

## 5、代码示例 ##

//先序遍历
    void PreOrderBiTree(BiTree BT) {
    	if (BT)
    	{
    		VisitBiTree(BT);
    		PreOrderBiTree(BT->lChild);
    		PreOrderBiTree(BT->rChild);
    	}
    }

# 二、迭代（iteration） #

## 1、定义 ##

迭代是重复反馈过程的活动，其目的是为了逼近或求得所需目标或结果。

每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。

例如利用迭代法\*求某一数学问题的解。对计算机特定程序中需要反复执行的子程序\*(一组指令)，进行一次重复，即重复执行程序中的循环，直到满足某条件为止，亦称为迭代。

## 2、必要条件 ##

1. 问题可以转化为一个解决方案的重复操作，某次操作的输出是下次操作的输入；

## 3、优点 ##

1.可以将重复问题转化为单一问题重复操作，减少代码量。

2.代码运行效率高，时间只因循环次数增加而增加，但是没有额外的空间开销；

## 4、缺点 ##

代码不如递归简洁。

## 5、代码示例 ##

#include<iostream>
    using namespace std;
    
    //求根号2的近似值
    void main() {
    	float i = 1;
    	float j = 2;
    	float avg = (j + i) / 2;
    	while ((avg*avg - 2>0.000001)|| (2 - avg*avg>0.000001))
    	{
    		if (avg*avg > 2)
    		{
    			j = avg;
    		}
    		else
    			i = avg;
    		avg = (j + i) / 2;
    
    	}
    	
    	cout <<"根号 2  ≈ "<< avg << endl;
    	
    }

# 三、递归与迭代的联系 #

1。递归和迭代都是循环，通过不断重复执行某些操作，从而达到我们要求的结果。

2.他们都是将复杂重复问题简化，通过反复调用实现复杂功能。

# 四、递归与迭代的区别 #

1。递归是不断调用自身，假设递归自己是一个函数的话，那递归的返回值会当作参数再次传入自身。迭代是将某一个初值设定，不断放入某一个循环体，得到的值成为一个新值再次放入循环体中，通过循环体中的操作，逐步得到我们想要的结果。总结一下就是：**程序调用自身称为递归，利用变量的原值推出新值称为迭代**。

2.举个不太恰当的例子，递归像是走在魔法森林，不管怎么走，都会回到同一个地方，再走一次，再走一次。迭代像是打磨一件工艺品，打磨一次，看看效果，接着打磨，再看看效果，直到满意为止。

3.**递归是自己调用自己,迭代就是自己调用别人**。

4.**递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换**，少部分只能用迭代，很难用递归。

[Link 1]: https://blog.csdn.net/shuiyixin/article/details/83187900