迭代和递归的理解和区别_如何判断递归和迭代[通俗易懂]

迭代和递归的理解和区别_如何判断递归和迭代[通俗易懂]最近做一些题经常会碰到迭代的方法解的,或者递归解法,容易搞混,特在此整理一下一.递归:由例子引出,先看看递归的经典案例都有哪些1.斐波那契数列斐波纳契数列,又称黄金分割数列,指的是这样一个

最近做一些题经常会碰到迭代的方法解的,或者递归解法,容易搞混,特在此整理一下
一.递归:
由例子引出,先看看递归的经典案例都有哪些
1.斐波那契数列
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……
这个数列从第三项开始,每一项都等于前两项之和。
2.
阶乘 n! = n * (n-1) * (n-2) * …* 1(n>0)
3.汉诺塔问题
在这里插入图片描述
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. 两张有意思的图
在这里插入图片描述
在这里插入图片描述
现在就算说不出定义也能理解什么是递归了

在这里插入图片描述
递归到底是个啥

递归,就是在运行的过程中调用自己。
构成递归需具备的条件:

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;  
} 

今天的文章迭代和递归的理解和区别_如何判断递归和迭代[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/72354.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注