Posted on 2007-02-20 12:56
dennis 阅读(1266)
评论(0) 编辑 收藏 所属分类:
数据结构与算法
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皇后问题中使用此技术。具体程序不再列出（好长@_@）