SICP 关于递归迭代的重新理解以及尾递归的引入...
2024-08-31 18:58:12
看了线性的递归和迭代以及树形递归迭代这部分的内容,感觉对递归和迭代又有了新的理解...所以记录一下,也算对这部分内容的总结吧.
首先书中提到的递归与迭代和我以前想的有点不一样,我感觉书中提到的递归和迭代是站在编译器/解释器的基础上来看的,而我之前是站在语言(类C语言的)的具体实现的角度看的.
理解这个需要先看书中提到的两个概念:
1.递归过程
2.递归的计算过程
可以用书中举出的阶乘的例子来看
实现1:
(factorial )
(* (factorial ))
(* (* (factorial )))
(* (* (* (factorial ))))
...
(* (* (* (* (* (factorial )))))) --->
实现2:
(factorial )
(fact-iter )
(fact-iter )
(fact-iter )
(fact-iter )
(fact-iter )
(fact-iter )
(fact-iter ) --->
实现1就是递归的计算过程, 实现2是迭代的计算过程.区别在于:从编译器的角度看, 实现1的实现需要系统维护以后将要执行操作的轨迹,随着递归深度的加深,所需要保存的信息量线性增长. 而对于实现2, 其状态可以用固定数量的状态变量进行描述.
换句话讲,在实现2中,过程中的任何一个点都提供了关于计算状态的完整描述.
c --> 递归计算过程
递归过程{ --> 迭代计算过程
scheme {
--> 递归计算过程
然而这两种实现从语言实现的角度来看(c), 都可以用递归实现, 也就都可以称做是递归过程. 然而c语言编译器这种对于递归的这种解释不论是空间效率和还是时间效率都是不尽人意的(在c语言的实现设计中,对于任何递归的解释都属于递归计算过程即使他们从原理上讲是迭代的),这也是为什么c语言有do...while/for 之类的循环结构的原因(对于scheme则不存在这个设计缺陷 --> scheme解释器采用了尾递归的技巧).
最新文章
- 响应式Web设计 - 布局
- 使用Markdown+Pandoc+LaTex+Beamer制作幻灯片
- 【零基础学习iOS开发】【02-C语言】09-流程控制
- Win32汇编环境配置
- iOS 实现脉冲雷达以及动态增减元素 By Swift-感谢分享
- 基于纯Java代码的Spring容器和Web容器零配置的思考和实现(3) - 使用配置
- 做一个牛XX的身份证号验证类(支持15位和18位)
- 解决alaert.builder二次调用报错的bug
- 解决MSSQL 2008不能用IP登录的问题
- Win32界面 主函数分析
- .net 获取配置文件AppSettings的键值
- $mount(“#app”)手动挂载
- kafka_2.11-0.10.0.1生产者producer的Java实现
- webVR全景图多种方案实现(pannellum,aframe,Krpano,three,jquery-vrview)
- 阿里云k8s服务springboot项目应用升级时出现502错误
- Excel 从字符串中提取日期值
- IONIC 页面之间传递参数
- 为免费app嵌入Admob广告
- sqlserver 2012隐藏查询结果窗口
- Oracle安装部署之 timesten install on redhat6.5