1。递归的定义:
递归的定义由两部分组成:
1)称作定位点(anchor)或者基本情况(ground case),它们是一些基本元素,这些基本元素是集合序列中其他所有对象的基础。
2)给出除基本元素或者已创建对象之外的新对象的构造规则,可以再三使用这个规则不断产生新的对象。
2。递归的实现:一般是由操作系统完成的,但是大部分的计算机系统的递归定义都是利用运行时堆栈实现的。在系统内,无论何时调用一个方法都会创建一个活动记录。一个递归调用并不仅仅是一个方法调用其自身,而是方法的一个instance调用相同方法的另一个instance,在计算机内部,这些调用是用不同的活动记录表示,并由系统区分。
3。尾递归:
仅在方法的末尾实行一次递归调用,这样的递归叫尾递归。尾递归很容易被循环所替换,或者说它只是一个名字比较好听的循环,如:
void tail(int i){
if(i>0){
System.out.print(i+" ");
tail(i-1);
}
} 替换为循环:
void tail2(int i){
for(;i>0;i--)
System.out.print(i+" ");
} 尾递归对一些没有显式循环结构的语言(如Prolog)特别重要
4。非尾递归:
递归相比于迭代结构的优点就是非常清晰并易于理解,这一点可以在二叉树遍历上得到体现。3种遍历方式的递归版本与迭代版本在可读性上不可同日而语。
问题:逆序输出一行输入(以ruby语言为例)
def reverse
s=STDIN.getc
if s.chr!="/n"
reverse
print s.chr
end
end
reverse 运行此程序,输入一行字符,将逆序输出,本质上是利用运行时堆栈完成的递归调用
5。间接递归:
方法通过一连串的调用,然后间接地调用它自身,这样的递归称为间接递归。
6。嵌套递归
一般出现在函数的定义中,如果这个函数不仅用它自身定义,而且还江它自身作为一个参数,如:
0 n=0
h(n)=n n>4
h(2+h(2n)) n<=4
7。过分递归:递归带来的逻辑简单性和可读性的代价是拖长了运行时间并且相对于非递归方法,它占用了更多的运行时堆栈空间。如果递归层次太深,可能导致运行时堆栈溢出,程序非正常结束的错误。
8。回溯(backtracking技术):在某点有多条道路供选择的时候,但不清楚哪一条能解决问题。在尝试一条道路失败后,返回岔口再试另一条道路。但是必须确定所有的道路都是可尝试的,可返回的。这种技术成为回溯。
在迷宫问题中和8皇后问题中使用此技术。具体程序不再列出(好长@_@)
分享到:
相关推荐
java 数据结构 递归 八皇后 完美递归 java 数据结构 递归 八皇后 完美递归
二叉树的中序、前序、后序的递归、非递归遍历算法
数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
数据结构和算法学习之递归
今天小编就为大家分享一篇基于Python数据结构之递归与回溯搜索,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
数据结构八皇后问题 eightqueens
数据结构 递归的定义、递归的调用过程以及各种递归算法的实现。以下三种情况用到递归:定义是递归的、 数据结构是递归的、 问题的解法是递归的
数据结构递归ppt,有助于初学者学习!很有用。
讲解非常详细,而且很容易理解!!!,并且在课件的后面还附加了课题,可以让你对上面的内容跟熟练。
数据结构,递归操作,主要运用栈,队列,链表等结构进行操作
在学习数据结构中自己实现的迷宫游戏。这个代码中有迷宫生成(迷宫比较不错),然后对生成的迷宫用递归算法寻找路径。在迷宫设计以及递归学习是个不错的选择。
数据结构实验二叉树用递归实现先序遍历、中序遍历和后序遍历,用几种不同非递归方法实现了中序遍历,代码附有详细注释
数据结构的递归入门,c语言版,有经典问题
数据结构课程中,采用堆栈的方式构造递归,并同时用递归函数进行结果验证。
数据结构与算法之递归,深入浅出,很深刻,很透彻。
1/输出n个整数的全排列。 2、输出n个整数的所有子集。
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).
数据结构 迷宫求解 c语言编写 ------------------- ------------------- -------------------
数据结构递归全文共2页,当前为第1页。数据结构递归全文共2页,当前为第1页。递归函数 数据结构递归全文共2页,当前为第1页。 数据结构递归全文共2页,当前为第1页。 递归函数就是直接或者间接调用自身的函数。 ...