来自HNUlanwei的CSDN:http://blog.csdn.net/u010911350
递归在很多时候被视为洪水猛兽。它的名声狼籍,好像永远和低效联系在一起。
其实,对一些如树的递归结构,递归算法是又自然又好用。
如果看看一些用来代替递归的技术,(汉诺塔的迭代算法不去说它,那是真正的算法的革命,除了佩服没啥好说的),一般来说只不过是自己模拟堆栈,编起来费劲,读起来费劲,维护起来更费劲。而模拟堆栈的效果,相比于简单的递归,好处在哪里呢?
1。不使用进程堆栈,不会耗尽堆栈空间(虽然可能耗尽堆空间)
2。可以有选择地把真正有用的东西压栈,而不用什么pc, sp, 所有的局部变量都压栈。这样节省了一些内存(不过,仍然在一个数量级,递归是O(N),模拟递归仍然是O(N))。 不过这也不绝对,编译器的优化可以识别一些不需要保存的局部变量的。(这叫变量生存期分析)
那么这样做又没有坏处呢?除了上面的代码复杂度的问题(我想很多搞嵌入式系统,实时系统的C高手都对此不屑一顾),还有一个效率上的缺点:
模拟的递归使用堆空间,它的new/delete都比直接在堆栈上分配空间慢得多。而且很容易产生内存碎片。
所以说,模拟堆栈只不过是牺牲了一定的效率来换取了一部分空间而已。是否值得,嘿嘿,就得看具体应用了。
好,闲话说完,下面言归正传。
话说大家都知道函数调用要压栈。不过这是有几个例外的。
1。函数是inline的。
2。语言采用的函数调用方式是continuation, 而不是activation record. 这种模式中语言可以使用堆而不是栈来完成函数调用。
3。尾调用。也就是说,函数调用出现在调用者函数的尾部,因为是尾部,所以根本没有必要去保存任何局部变量,sp, pc的信息。直接让被调用的函数返回时越过调用者,返回到调用者的调用者去。
比如:
f(){g();} g(){h();}
这里,h()函数返回时可以绕过g()函数,f()函数而直接返回到f()函数的调用者。
注意,尾调用优化不是什么很复杂的优化,实际上几乎所有的现代的高级语言编译器都支持尾调用这个很基本的优化。
实现层面上,只需要把汇编代码call改成jmp, 并放弃所有局部变量压栈处理,就可以了。所以,很简单。
我们不考虑continuation这种情况,因为c/c++/java等流行的语言都不是这种模式。
对于递归,inline也不能使用。因为你不知道你会递归调用多少次。
于是,就剩下递三条:尾调用。而一个对自己本身的递归尾调用,就叫做尾递归。
那么,当尾递归时,我们就没有前面分析的递归调用的占用堆栈的缺点,因为每次调用都是尾调用,所以堆栈根本就没有被占用,每次调用都是重新使用调用者的堆栈。
有些看过ml, haskell这种functional language的程序员可能会奇怪为什么他们不支持循环。
现在让我们看看他们会怎么实现循环的功能。
考虑一个简单的例子,求从一加到一百的和。
用递归, 我们也许可以这样做:
//普通递归 int sum(int start,int end) { if(start>end) return 0; else return start+sum(start+1,end); }
这个递归函数是可以工作的,唯一的缺点是它会占用很多堆栈空间,也会有很大的压栈出栈的开销。
于是,我们用尾递归:
//尾递归 int tail_sum(int seed,int start,int end) { if(start>end) return seed; else return tail_sum(seed+start,start+1,end); }
小小的修改,sum变成了尾递归,没有了对堆栈空间的占用,也没有任何压栈开销。
注意,这里尾调用的“尾”字,是指运行时需要执行的最后一个动作。不是简单的语法字面上的最后一个语句。
比如说,c++中,如果我的sum返回的不是int, 而是一个带有有副作用的析构函数的类,那么它就不再是尾递归:
X sum(X seed, X start, X end){ if(start<end) return seed; else return sum(seed+start, start+1, end); }
几乎同样的代码,只是不同的类型,但这里,它已经不再是尾递归了!
即使这个X类的拷贝构造和析构函数里面通过所有权转移,move semantics减小了拷贝和析构的开销,但,副作用就是副作用,它不再是尾调用了。
分析了一大堆,那么尾递归到底有什么好处呢?呵呵,可读性好,代码强壮,易维护。
另外,不是所有的递归都可以变成尾递归的。
最后附上Fibonacci数列求解的尾递归:
//普通递归 int Fibonacci(int n) { if(n<2) return n; else return Fibonacci(n-2)+Fibonacci(n-1); } //尾递归 int tail_Fibonacci(int n,int a1,int a2) { if(n==0) return a1; else return tail_Fibonacci(n-1,a1+a2,a1); }
过程模拟请见:http://www.cnblogs.com/Anker/archive/2013/03/04/2943498.html
相关推荐
面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和队列) 5 面试题 6:旋转数组的最小数字(考点:...
例子倒数至零一个简单的尾递归函数,倒数为零:前后static void count( int n) { if (n == 0 ) { return ; } count(n - 1 ); } static void count( int n) { while ( true ) { if (n == 0 ) { return ; } n = n - 1 ...
题6:从尾到头打印链表 解法:栈 或者 递归 题7:重建二叉树 解法:递归。每次先找根结点,然后递归左子结点和右子结点。 题8:二叉树的下一个结点 解法1:分3类讨论。有右子树;是父节点的左节点;父节点的右节点则...
面试题06:从尾到头打印链表 +2 栈+双数组 面试题07:重建二叉树 +2 递归 面试题09:用两个栈实现队列 +2 双栈 面试题10 - I:斐波那契数列 +2 动态规划+递归 面试题10 - II:青蛙跳台阶问题 +2 动态规划+递归 面试...
若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9,比23小,则首位置更新为...
替换后会导致下面的子树发生了变化,因此同样需要进行比较,直至各个节点实现父>子这么一个条件(递归) 交换排序 冒泡排序 思想 每次俩俩交换,将最大值交换到末尾 做法 ...
leetcode 各平台的价格区间 Sword2Offer :check_mark: 1. 二维数组中的查找 类似二分查找 public boolean Find(int ...从尾到头打印链表 递归 func PrintListTailToHead(listNode *Node) { //for current
19.8 替换string中的字符 19.9 在string中插入字符 19.10 转换成C语言式char 字符串 19.11 迭代器 19.12 字符串流处理 小结 术语 自测练习 自测练习答案 练习 第20章 标准模板库(STL) 20.1 标准模板库(STL)...
19.8 替换string中的字符 19.9 在string中插入字符 19.10 转换成C语言式char 字符串 19.11 迭代器 19.12 字符串流处理 小结 术语 自测练习 自测练习答案 练习 第20章 标准模板库(STL) 20.1 标准模板库(STL)...
1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 177 ∷相关函数:InOrderTraverse2函数 1.4.12 后序遍历二叉树(顺序结构) 180 范例1-66 后序遍历二叉树 180 ∷相关函数:...
1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 177 ∷相关函数:InOrderTraverse2函数 1.4.12 后序遍历二叉树(顺序结构) 180 范例1-66 后序遍历二叉树 180 ∷相关函数:...
1.4.11 中序非递归遍历二叉树(链式结构)(2) 177 范例1-65 中序非递归遍历二叉树 177 ∷相关函数:InOrderTraverse2函数 1.4.12 后序遍历二叉树(顺序结构) 180 范例1-66 后序遍历二叉树 180 ∷相关函数:...
从尾到头打印链表 链表 4 重建二叉树 树 5 用两个栈实现队列 栈和队列 LeetCode 232 6 旋转数组的最小数字 查找和排序 LeetCode 153 7 斐波那契数列 递归和循环 LeetCode 509 8 跳台阶 递归和循环 LeetCode 70 9 ...
从尾到头打印链表 易 树 重建二叉树 难 递归和循环 斐波那契数列 易 递归和循环 跳台阶 中 递归和循环 变态跳台阶 中 递归和循环 矩形覆盖 中 位运算 二进制中1的个数 易 代码的鲁棒性 链表中倒数第k个结点 中 代码...
6、从尾到头打印链表(栈、递归) √ 18、删除链表的节点 22、链表中倒数第k个节点 24、反转链表 25、合并两个排序的链表 52、两个链表的第一个公共节点 整数拆分(多少种分法)√ 整数拆分(最大乘积)√ 青蛙过河 √...
1. 替换空格 2. 从尾到头打印链表 3. 用两个栈实现队列 4. 判断字符串是否表示数值 5. 反转链表 1. 迭代 2. 递归 6. 包含min函数的栈
range.js 定义了一个经典的命令式实现——即方法是使用循环定义的,而 rangeFn.js 提供了一个使用尾递归函数的“函数式”实现。 (在后者的情况下,如果运行时不提供尾调用优化,堆栈可能会爆炸,因此目前可以考虑...
chmod u/g/o/a +/-/= /r/w/x file name 改权限 -r 递归改 R 100=4 W 010=2 X 001=1 数字表示法 chown user file 改文件所有用户 chown user。group file 改文件的用户与所属组 chgrp group file 改文件所有组 ...
另一种方法是使用"//",从"//"开始,直到它所在行的行尾,所有字符都被作为注释处理。 2-8 什么叫做表达式?x = 5 + 7是一个表达式吗?它的值是多少? 解: 任何一个用于计算值的公式都可称为表达式。x = 5 + 7是一...
第 1 章- 表达式、命名和环境、评估组合、复合过程、替换模型、应用顺序评估、正常顺序评估、条件表达式和谓词、数值分析、平方根、立方根、黑盒抽象、递归、迭代、线性递归、树递归、生长阶数、求幂、最大公约数、...