迭代和递归的理解和区别

痛定思痛。 2022-02-02 23:57 347阅读 0赞

最近做一些题经常会碰到迭代的方法解的，或者递归解法，容易搞混，特在此整理一下  
**一.递归：**  
由例子引出，先看看递归的经典案例都有哪些  
**1**.斐波那契数列  
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……  
这个数列从第三项开始，每一项都等于前两项之和。  
**2.**  
阶乘 n! = n \* (n-1) \* (n-2) \* …\* 1(n>0)  
**3**.汉诺塔问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70]  
**4**.全排列  
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。  
如1,2,3三个元素的全排列为：  
1,2,3  
1,3,2  
2,1,3  
2,3,1  
3,1,2  
3,2,1  
**5**. 两张有意思的图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 2]  
现在就算说不出定义也能理解什么是递归了

![在这里插入图片描述][20190508125015681.png]  
**递归到底是个啥**

**递归，就是在运行的过程中调用自己。  
构成递归需具备的条件：**  
**1. 子问题须与原始问题为同样的事，且更为简单；  
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。**

**二.迭代**  
迭代的经典例子  
1.斐波那契数列（没错，又是我）  
2.汉诺塔问题（这不巧了么）  
3.背包问题  
有N件物品和一个容量为V的背包。第i件物品的重量是w\[i\]，价值是v\[i\]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。基本思路  
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。  
用子问题定义状态：即f\[i\]\[v\]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：  
f\[i\]\[v\]=max\{ f\[i-1\]\[v\], f\[i-1\]\[v-w\[i\]\]+v\[i\] \}。  
可以压缩空间，f\[v\]=max\{f\[v\],f\[v-w\[i\]\]+v\[i\]\}  
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f\[i-1\]\[v\]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w\[i\]的背包中”，此时能获得的最大价值就是f \[i-1\]\[v-w\[i\]\]再加上通过放入第i件物品获得的价值v\[i\]。  
注意f\[v\]有意义当且仅当存在一个前i件物品的子集，其费用总和为f\[v\]。所以按照这个方程递推完毕后，最终的答案并不一定是f\[N\] \[V\]，而是f\[N\]\[0…V\]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f\[v-1\]，这样就可以保证f\[N\] \[V\]就是最后的答案。  
**同样的例子，做法不同，也就有了不同的定义**  
**迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。**

迭代和递归的关系和区别（敲黑板）  
从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。简单地说，递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环，而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。  
**迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。**  
**递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)**。  
在循环的次数较大的时候，迭代的效率明显高于递归。  
以斐波那契数列的求解为例，通过两种典型的实现进行对比：  
递归的实现

int fib(int n){  
             if(n>1) return fib(n-1) + fib(n-2);  
             else return n; // n = 0, 1时给出recursion终止条件  
        }

迭代

int fib(int n){  
        int i, temp0, temp1, temp2;        
        if(n<=1) return n;  
        temp1 = 0;  
        temp2 = 1;  
        for(i = 2; i <= n; i++){  
            temp0 = temp1 + temp2;  
            temp2 = temp1;  
            temp1 = temp0;  
        }  
        return temp0;  
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70]: /images/20220203/ad8b98ce11404c729e642ad6d9b16c39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 1]: /images/20220203/cbc78ecb234c4900a72b0d2e1e73fd70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 2]: /images/20220203/b1f8ad09504b40d7aec78558826edb1a.png
[20190508125015681.png]: /images/20220203/a62735cdc11a4cdaa90b0c88af3f05aa.png