数据结构之递归
2023-03-09 22:24:19 时间
1。递归的定义:
递归的定义由两部分组成:
1)称作定位点(anchor)或者基本情况(ground case),它们是一些基本元素,这些基本元素是集合序列中其他所有对象的基础。
2)给出除基本元素或者已创建对象之外的新对象的构造规则,可以再三使用这个规则不断产生新的对象。
2。递归的实现:一般是由操作系统完成的,但是大部分的计算机系统的递归定义都是利用运行时堆栈实现的。在系统内,无论何时调用一个方法都会创建一个活动记录。一个递归调用并不仅仅是一个方法调用其自身,而是方法的一个instance调用相同方法的另一个instance,在计算机内部,这些调用是用不同的活动记录表示,并由系统区分。
3。尾递归:
仅在方法的末尾实行一次递归调用,这样的递归叫尾递归。尾递归很容易被循环所替换,或者说它只是一个名字比较好听的循环,如:
替换为循环:
尾递归对一些没有显式循环结构的语言(如Prolog)特别重要
4。非尾递归:
递归相比于迭代结构的优点就是非常清晰并易于理解,这一点可以在二叉树遍历上得到体现。3种遍历方式的递归版本与迭代版本在可读性上不可同日而语。
问题:逆序输出一行输入(以ruby语言为例)
递归的定义由两部分组成:
1)称作定位点(anchor)或者基本情况(ground case),它们是一些基本元素,这些基本元素是集合序列中其他所有对象的基础。
2)给出除基本元素或者已创建对象之外的新对象的构造规则,可以再三使用这个规则不断产生新的对象。
2。递归的实现:一般是由操作系统完成的,但是大部分的计算机系统的递归定义都是利用运行时堆栈实现的。在系统内,无论何时调用一个方法都会创建一个活动记录。一个递归调用并不仅仅是一个方法调用其自身,而是方法的一个instance调用相同方法的另一个instance,在计算机内部,这些调用是用不同的活动记录表示,并由系统区分。
3。尾递归:
仅在方法的末尾实行一次递归调用,这样的递归叫尾递归。尾递归很容易被循环所替换,或者说它只是一个名字比较好听的循环,如:
void tail(int i){
if(i>0){
System.out.print(i+" ");
tail(i-1);
}
}
if(i>0){
System.out.print(i+" ");
tail(i-1);
}
}
替换为循环:
void tail2(int i){
for(;i>0;i--)
System.out.print(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
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皇后问题中使用此技术。具体程序不再列出(好长@_@)
文章转自庄周梦蝶 ,原文发布时间5.17
相关文章
- A/B测试助力游戏业务增长
- 基线监控:基于依赖关系的全链路智能监控报警
- 在字节跳动,一个更好的企业级SparkSQL Server这么做
- 揭露ROI提升5倍的秘密!火山引擎A/B测试白皮书重磅发布(内附下载链接)
- 字节跳动构建Data Catalog数据目录系统的实践
- 基于Feature Flag的下一代开发模式
- 揭秘字节跳动云原生Spark History 服务 UIService
- 来看看字节跳动内部的数据血缘用例与设计
- 看SparkSql如何支撑企业数仓
- ClickHouse 在 UBA 系统中的字典编码优化实践
- 在字节,A/B 实验是这么做的!
- Geekbench 6 for Mac(检测系统性能工具) v6.0.0免激活版
- 曲终人散!Mavell公司“巧妙”收购Innovium
- 可编程网络加持,何惧无人机“炸机”撞楼!
- 云数据中心网络现状:100G捕蝉,800G在后
- Image2icon for Mac(icon图标设计软件)
- MySql常用函数(逻辑判断,字符串处理,日期函数)FIND_IN_SET、IF、ISNULL、IFNULL、NULLIF、SUBSTR、SUBSTRING_INDEX、CONCAT、LENGTH
- SpringSecurity-从入门到精通
- hibernate-validator校验参数(统一异常处理)
- WordPress 的下载和安装