以图明志

计算机算法

漫谈递归:从汇编看尾递归的优化

尾递归的编译器优化
对于尾递归,很多人的理解仅局限于它是递归和尾调用的一个合体,比普通递归效率高。至于效率为什么高,高在哪,可能没有深究过。 在执行函数B时,函数A的栈帧其实是已经大部分没用了,可以被修改或覆盖。编译器可以利用这一点进行优化,函数B执行后直接返回到函数A的调用者。

计算机算法

漫谈递归:PHP里的尾递归及其优化

PHP编译器没有对尾递归进行优化
事实证明,尾递归在php中是没有任何优化效果的。一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的,即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化,比如C语言对尾递归的优化。

计算机算法

漫谈递归:补充一些Continuation的知识

Continuation在函数式编程是非常自然的
Continuation是一种非常古老的程序结构,简单说来就是entire default future of a computation, 即对程序“接下来要做的事情”所进行的一种建模,即为“完成某件事情”之后“还需要做的事情”。而这种做法,也可以体现在尾递归构造中。在函数式语言中,continuation的引入是非常自然的过程。

计算机算法

漫谈递归:尾递归与CPS

尾递归就是Continuation Passing Style
与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。

计算机算法

漫谈递归:从斐波那契开始了解尾递归

对尾递归的大概了解
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数,如果在递归函数中,递归调用返回的结果总被直接返回,则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言,而且从编译器角度来说,亦容易优化成为普通循环。这是因为从电脑的基本面来说,所有的循环都是利用重复移跳到代码的开头来实现的。

编程思想

递归计算过程与迭代计算过程

编程需要了解的基础知识
递归是实现程序计算过程中的描述过程的基本模式之一,在讨论递归的问题前我们必须十分小心,因为递归包含两个方面的内容,一个是递归的计算过程,一个是递归过程,后者是语法上的事实而前者是概念上的计算过程,事实上在程序上我们也许是使用循环来实现的。

计算机算法

漫谈递归:循环与迭代是一回事吗?

理清递归、迭代、循环的概念
迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。个人认为迭代是循环的一种,循环体代码分为固定循环体,和变化的循环体。

计算机算法

漫谈递归:递归与循环

大部分递归可以转化为循环
大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。递归是利用系统的堆栈保存函数当中的局部变量来解决问题的。递归说白了就是在栈处理栈上一堆的指针指向内存中的对象,这些对象一直不被释放,直到递归执行到最后一次跳出条件的时候,才一个个出栈。所以开销很大。

计算机算法

漫谈递归:递归的效率问题

效率和开销问题是递归最大的缺点
递归在解决某些问题的时候使得我们思考的方式得以简化,代码也更加精炼,容易阅读。那么既然递归有这么多的优点,我们是不是什么问题都要用递归来解决呢?难道递归就没有缺点吗?今天我们就来讨论一下递归的不足之处。谈到递归就不得不面对它的效率问题。

计算机算法

漫谈递归:二分查找算法的递归实现

用递归写一个二分查找
还有一个典型的递归例子是对已排序数组的二分查找算法。现在有一个已经排序好的数组,要在这个数组中查找一个元素,以确定它是否在这个数组中,很一般的想法是顺序检查每个元素,看它是否与待查找元素相同。这个方法很容易想到,但它的效率不能让人满意,它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

计算机算法

漫谈递归:字符串回文现象的递归判断

回文符合递归的两个条件
回文是一种字符串,它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢?如果一个字符串是回文,那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且,我们注意到,一个回文的第一个字符和最后一个字符一定是相同的。

计算机算法

漫谈递归:递归需要满足的两个条件

还是拿斐波那契数列来做例子
递归,并不是简单的“自己调用自己”,也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说,递归的思想就是:把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法,就是不断地把问题的规模变小(变成原问题的一半),而新问题与原问题有着相同的解法。

计算机算法

漫谈递归:递归的思想

用归纳法来理解递归
很多不理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环,大家都知道递归分两步,递和归,那么可以知道递归对于空间性能来说,简直就是造孽,这对于追求时空完美的人来说,简直无法接接受,如果递归仅仅是循环,估计现在我们就看不到递归了。
1 / 1 首页 < Prev 1 Next > 尾页 页码: