大家都知道,递归的本质和栈数据的存取很相似了,都是先进去,但是往往最后处理!再者对于递归函数的局部变量的存储是按照栈的方式去存的,对于每一层的递归函数在栈中都保存了本层函数的局部变量,一边该层递归函数结束时能够保存原来该层的数据!如图:
如上图递归式依次往下进行的,并且在该层递归函数还没结束即将进入下一层递归调用时,将会把该层函数中的局部变量保存起来,以供下次使用!
好了,以上是递归函数的数据存储方式,可是有时候我们又得抓头了,递归的话,有时候又很难理解,貌似总也想不通!
于是我又把每一层递归函数化分为三部分了,第一部分:是递归调用前的一些数据处理,判断以及递归结束判断(当然了结束条件肯定在递归调用前,要不每次递归就不会结束了),第二部分:就是递归函数本身了。而第三部分:当然就是递归函数的后续处理代码了!在这里我想我们得想明白一件事情了,每一层的函数都是在上一层递归函数结束时才返回的然后接着处理该层递归函数剩下的部分!例如如下代码:
#include<iostream> #include<string> using namespace std; int i=0,j; void reverse(string &s); int main() { string s; cin>>s; j=i=s.size(); reverse(s); cout<<s<<endl; return 0; } void reverse(string &s) { char ch; //..........第一部分 .......... i--; ch=s[i]; cout<<ch<<endl; //这里i是全局变量,而ch是局部变量会保存在栈中 if(-1==i) return; reverse(s); //本身的递归看做第二部分 //后续部分看做第三部分 s[--j]=ch; //这句当且仅当该递归函数中的reverse返回时 才执行 cout<<ch<<endl; }
在以上代码中,每一层只有当reverse()结束了才会接着处理下面的s[--j]=ch;代码,因为每一次递归进去的时候reverse()上面的代码都已经处理了,所以当递归返回时处理的自然就是reverse()下面的代码了,如此循环直到结束!不过我觉着最重要的还有一样就是有时候不必刻意去关注的那么细,也要有全局观,例如我们只需要知道函数reverse()是继续处理同样的功能,没必要再去想这个函数里面又是怎么样怎么样的,我感觉肯定会抓狂的!希望跟我一样纠结的朋友不在纠结递归了.........
另外,
递归的使用条件:
存在一个递归调用的终止条件;
每次递归的调用必须越来越靠近这个条件;只有这样递归才会终止,否则是不能使用递归的!
总之,在你使用递归来处理问题之前必须首先考虑使用递归带来的好处是否能补偿
他所带来的代价!否则,使用迭代算法会比递归算法要高效。
递归的基本原理:
1 每一次函数调用都会有一次返回.当程序流执行到某一级递归的结尾处时,它会转移到前一级递归继续执行.
2 递归函数中,位于递归调用前的语句和各级被调函数具有相同的顺序.如打印语句 #1 位于递归调用语句前,它按照递归调用的顺序被执行了 4 次.
3 每一级的函数调用都有自己的局部变量.
4 递归函数中,位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反.
即位于递归函数入口前的语句,右外往里执行;位于递归函数入口后面的语句,由里往外执行。
5 虽然每一级递归有自己的变量,但是函数代码并不会得到复制.
6 递归函数中必须包含可以终止递归调用的语句.
一旦你理解了递归(理解递归,关键是脑中有一幅代码的图片,函数执行到递归函数入口时,就扩充一段完全一样的代码,执行完扩充的代码并return后,继续执行前一次递归函数中递归函数入口后面的代码),阅读递归函数最容易的方法不是纠缠于它的执行过程,而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误,你的限制条件设置正确,并且每次调用之后更接近限制条件,递归函数总是能正确的完成任务。
不算递归调用语句本身,到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行,所以它的效果类似循环:当quotient的值非零时,把它的值作为初始值重新开始循环。但是,递归调用将会保存一些信息(这点与循环不同),也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。
斐波那契数是典型的递归案例:
Fib(0) = 0 [基本情况] Fib(1) = 1[基本情况]
对所有n > 1的整数:Fib(n) = (Fib(n-1) + Fib(n-2))[递归定义]
递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历,图的搜索)
如:
procedure a;
begin
a;
end;
这种方式是直接调用.
又如:
procedure b;
begin
c;
end;
procedure c;
begin
b;
end;
这种方式是间接调用.
如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
Ref:
http://blog.csdn.net/zp032420/article/details/7422158
http://www.cnblogs.com/jnje/archive/2011/04/09/2010637.html
相关推荐
深入理解分治法的算法思想,应用分治法解决实际的算法问题。 【实验性质】 验证性实验(学时数:2H) 【实验内容与要求】 1、设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴每个选手...
递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面对此方面进行更加深入的理解 递归的分类 这里根据递归调用的数量分为线性递归、二路递归与多重递归 线性递归 如果...
熟悉递归并深入了解递归的工作原理对于确保您准备给招聘经理留下深刻的印象至关重要,并且(最终)可以为工程团队做出重要贡献。 说明和/或完成要求 以递归方式在中实现二进制搜索算法。 通过运行test_searching....
计的程序结构比较简洁和清晰,但递归算法是较难理解和掌握的,因此,对递归算法的概念及结构进行深入分析, 给出递归算法的设计方法,并通过对递归算法的内部实现过程的描述,可以帮助学生正确理解和应用递归算法解 决实际...
熟悉递归并深入了解递归的工作原理对于确保您准备给招聘经理留下深刻的印象至关重要,并且(最终)可以为工程团队做出重要贡献。 说明和/或完成要求 [x]以递归方式在中实现二进制搜索算法。 通过运行test_...
本篇文章是对二叉树的非递归遍历进行了详细的分析介绍,需要的朋友参考下
下面小编就为大家带来一篇深入理解python函数递归和生成器。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
该资源包括实用练习,让读者可以练习在Java中实现递归阶乘,并提供解决方案以帮助读者检查自己的工作并深入理解所学内容。 无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,...
一个经典的题————汉诺塔的C语言实现。运用了递归算法实现很简单。主要是思路,也可以通过这个来深入理解递归算法~
递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题;终止条件保证了程序的有穷性。 递归的应用有很多,常见的包括:阶乘运算、斐波那契数列、汉诺塔、数的遍历,...
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,需要的朋友可以参考下
1、熟悉二叉线索树的基本操作 2、深入了解递归在二叉树中的应用 1、建立中序线索二叉树,并实现对二叉树的中序遍历,并将结 2、仍沿用上面的数据,判断一个节点是否
因此这一篇文章,我将通过一些经典的通过递归算法实现的实例来更深入的了解递归算法。 汉诺塔问题 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根...
数据基本结构设计计算机编程中加工处理的对象是数据,而数据具有一定的组织结构,所以学习编写程序仅仅了解计算机语言是不够的,还必须掌握数据组织、储存和运算的一般方法。在掌握了这些基础方法的前提下,才能灵活...
递归神经网络(RNN)是一种强大的工具,可用于序列建模和处理各种时序数据。通过本讲义,你将了解RNN的基本原理、结构、应用和训练方法,并能够使用深度学习框架...希望这个讲义能够为你提供深入理解RNN的基础知识。
参加工作已经三四年了,再回头来看这些很基础的东西,觉得理解又深入了一层! 解释:程序调用自身的编程技巧叫做递归。 程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中...
但是如果你对函数式编程感兴趣,想深入理解一些核心概念,你应该读下去。 今年年初我开始学 Haskell 的时候,我被函数式代码的优雅和简洁俘获了。代码居然还能这样写!用指令式代码要写一堆的程序,用递归几行就...