谁可以给我说说栈与递归 栈的详细关系

来源：蜘蛛抓取(WebSpider) 时间：2017-11-16 05:29 标签： 栈与递归
没有更多推荐了，
不良信息举报
举报内容：
数据结构之---栈和递归&函数调用
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！一文读懂递归算法
我的图书馆
一文读懂递归算法
递归的学习绝对是一个持久战，没有人可以一蹴而就。一年两年的，很寻常。问题的复杂，加上递归本身的细节，我们想要 '学会'，'学好'，再 '用好'，是需要一个漫长的过程的。所以还希望读者有足够的耐心。一：什么是递归所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。我们可以把” 递归 “比喻成 “查字典 “，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。（摘自知乎的一个回答）我们以阶乘作为：int&Factorial(int&n){& &&&&&&&&if&(n&==&0)&&return&1;&&& & &&return&&&&&&n&*&Factorial(n&-&1);}二：递归与栈的关系常常听到 “递归的过程就是出入栈的过程”，这句话怎么理解？我们以上述代码为例，取&<span data-mathml="n=3" role="presentation">n=3，则过程如下：第 1~4 步，都是入栈过程，Factorial(3)调用了Factorial(2)，Factorial(2)又接着调用Factorial(1)，直到Factorial(0)；第 5 步，因 0 是递归结束条件，故不再入栈，此时栈高度为 4，即为我们平时所说的递归深度；第 6~9 步，Factorial(0)做完，出栈，而Factorial(0)做完意味着Factorial(1)也做完，同样进行出栈，重复下去，直到所有的都出栈完毕，递归结束。每一个递归程序都可以把它改写为非递归版本。我们只需利用栈，通过入栈和出栈两个操作就可以模拟递归的过程，二叉树的遍历无疑是这方面的代表。但是并不是每个递归程序都是那么容易被改写为非递归的。某些递归程序比较复杂，其入栈和出栈非常繁琐，给编码带来了很大难度，而且易读性极差，所以条件允许的情况下，推荐使用递归。三：如何思考递归在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的验证之中，比如上面提及的阶乘，求解Factorial(n)时，我们总会情不自禁的发问，Factorial(n-1)可以求出正确的答案么？接着我们就会再用Factorial(n-2)去验证，，，不停地往下验证直到Factorial(0)。对递归这样的不适应，和我们平时习惯的思维方式有关。我们习惯的思维是：已知Factorial(0)，乘上 1 就等于Factorial(1)，再乘以 2 就等于Factorial(2)，，，直到乘到 n。而递归和我们的思维方式正好相反。那我们怎么判断这个递归计算是否是正确的呢？Paul Graham&提到一种方法，如下：如果下面这两点是成立的，我们就知道这个递归对于所有的 n 都是正确的。当&<span data-mathml="n=0,1" role="presentation">n=0,1&时，结果正确；假设递归对于&<span data-mathml="n" role="presentation">n&是正确的，同时对于&<span data-mathml="n+1" role="presentation">n+1&也正确。这种方法很像数学归纳法，也是递归正确的思考方式，上述的第 1 点称为基本情况，第 2 点称为通用情况。在递归中，我们通常把第 1 点称为终止条件，因为这样更容易理解，其作用就是终止递归，防止递归无限地运行下去。下面我们用两个例子来具体说明这种数学归纳法：例 1 汉诺塔展开目录问题描述为：有三根杆子 A，B，C。A 杆上有 N 个穿孔圆盘，盘的尺寸由上到下依次变大，B，C 杆为空。要求按下列规则将所有圆盘移至 C 杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。问：如何移？最少要移动多少次？首先看下基本情况，即终止条件：N=1 时，直接从 A 移到 C。再来看下通用情况：当有 N 个圆盘在 A 上，我们已经找到办法将其移到 C 杠上了，我们怎么移动 N+1 个圆盘到 C 杠上呢？很简单，我们首先用将 N 个圆盘移动到 C 上的方法将 N 个圆盘都移动到 B 上，然后再把第 N+1 个圆盘（最后一个）移动到 C 上，再用同样的方法将在 B 杠上的 N 个圆盘移动到 C 上，问题解决。代码如下：void&Hanoi(int&n,&char&a,&char&b,&char&c){&&&&//终止条件&&&&if&(n&==&1)&&&&{&&&&&&&&&cout&&&a&&&'--&'&&&c&&&endl;&&&&&&&&&&&&&&&&&return;&&&&}&&&&//通用情况&&&&Hanoi(n&-&1,&a,&c,&b);&&&&Hanoi(1,&a,&b,&c);&&&&Hanoi(n&-&1,&b,&a,&c);}例 2 求二叉树节点个数展开目录首先看下基本情况，即终止条件：当为空树时，节点数为 0；再来看下通用情况：当前节点的左，右子树节点数都被求出，则以当前结点为根的二叉树的节点总数就是 “左子树 + 右子树 + 1”。代码如下：int&GetNodes(Node&*&node){&&&&//终止条件&&&&if&(node&==&nullptr)&&&&&&return&0;&&&&//通用情况&&&&return&&&&&&GetNodes(node-&left)&+&GetNode(node-&right)&+&1;}四：什么时候该用递归当我们遇到一个问题时，我们是怎么判断该题用递归来解决的？问题可用递归来解决需具备的条件：子问题需与原问题为同样的事，且规模更小；程序停止条件。
TA的最新馆藏
喜欢该文的人也喜欢扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
java 选择题解答关于方法的递归算法，说法正确的是()A．递归就是方法自己调用自己B．递归的次数不能过大，否则会导致栈内存溢出C．使用递归算法，方法必须有返回值D．构造方法不可以使用递归算法
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
尾递归优化C
不是必须的D
构造方法递归调用自己？不能吧
为您推荐：
扫描下载二维码博客访问： 2445327
博文数量： 315
博客积分： 10458
博客等级： 上将
技术积分： 4297
注册时间：
分类： C/C++ 18:03:13
本文从递归函数参数的角度来分析，递归函数调用时递归工作栈中工作记录减肥的可能性。用最简单的求阶层函数来举例：n! = n*(n-1)*(n-2)***2*1常见的递归实现如下：int fun(int n){&&&&& if( n<=1 ) return 1;&&&&& return n*fun(n-1);}不用多说，这个实现下每次递归调用都会在当前层的工作记录中分配一个4字节（IBM兼容机）的空间来存放n的值。若栈的深度为DEPTH，那么一共需要DEPTH×4个字节存放参数。那么能不能避免这些存储空间呢，我们来看看引用的情况：int fun(int &n){&&&&& if( n<=1 ) return 1;&&&&& return n*fun(n-1);}这段代码编译不能通过，原因是n-1只是一个右值。这里简单介绍一下c＋＋中的无名对象（变量）。c＋＋中的无名对象与const常量有些相似，他们都只能做右值而不能做左值，区别是const常量是有地址的可以取地址，而无名对象一般是不可以的。这里n－1有点无名对象的味道，因为fun要求一个变量引用。由于n－1是右值，所以把参数类型改成int fun(const int & n)就可以了。int fun(const int &n){&&&&& if( n<=1 ) return 1;&&&&& return n*fun(n-1);}现在运行通过了，但是栈空间需求仍然没有减少，因为引用的是无名对象，无名对象只是寄存器中的一个值，是没有RAM地址的。所以每递归调用一次，就会在工作记录中分配空间来存放n－1，实际效果相当于const int n = n-1;那么换个思路。以上程序之所以如此是因为传给递归函数的不是n本身，现设计如下：int fun(const int & n){&&&&& cout<<(long)&n<<&&&&& if( n<=1 ) return 1;&&&&& --n;&&&&& return (n+1)*fun(n);}这个程序运行正确而且所有的n确实是最外面的那个n的引用（打印的地址均一致）。有些人会怀疑这个程序不能正确的求出n!。想想也对，当递归不断深入到最里层的时候n＝1，递归回退的时候n仍然还是1，那结果不就成了1×2×2×2××××2了么？？您可以试试看，结果可能出乎您的预料：计算出的确实是 n! 原因如下：每调用一层时先计算n+1，n＋1的结果保存在register中，进入下一层递归前编译器会把适当的register的值压栈以便日后恢复，这里某个寄存器就存放着运算的中间结果n+1。日后返回该层时虽然此时n确实是1，但是n＋1的结果已经计算过，所以只是从栈顶取出n+1而非重新计算。作为思考，您可以试试看将(n+1)*fun(n)改成fun(n)*(n+1)，它将得出错误的结果。看来，递归调用函数使用引用参数和普通使用引用参数的非递归调用函数是有区别的：并不是使用了引用参数后就一定能够节省栈的空间，这取决于具体的递归函数（复杂。。。^_^）当然，在递归函数中使用引用参数还有一种目的，当然是为了改变实参的数值罗。对于非内部类型的对象而言，使用引用往往可以既节省空间又同时可以修改实参的值，这里就不再举例了。
阅读(3102) | 评论(0) | 转发(0) |
给主人留下些什么吧！~~
请登录后评论。

我要回帖

更多关于 栈与递归 的文章

 

随机推荐