以图明志

计算机算法

[专题] 漫谈递归: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里面看到一个初学者的留言),总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环,大家都知道递归分两步,递和归,那么可以知道递归对于空间性能来说,简直就是造孽,这对于追求时空完美的人来说,简直无法接接受,如果递归仅仅是循环,估计现在我们就看不到递归了。

数据结构

[专题] 栈是如何实现递归的

递归与栈一些不得不说的事
在高级语言中,调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。

数据结构

[专题] 递归,栈的重要应用之一

了解递归的一些细节
栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个 “化身”。一连串的“像中像” 这是一种递归现象。

计算机算法

用递归实现的快速排序

快速排序的两种不同实现
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归或者非递归进行,以此达到整个数据变成有序序列。

PHP服务器脚本

递归遍历PHP多维数组

二维及多维数组的遍历
数组的遍历是PHP一个常见的编程任务,而数组又分为一维数组、二维数组和多维数组。一维数组的遍历很简单,直接一个for循环就可以完成。那么二维数组和多维数组的遍历又应该如何实现呢?请看以下程序……

计算机算法

在数字前面补0的几个实现思路

一个问题的多个思路
要求1-9的数字前面加0,如01 02 ....10 11....,就是用 JavaScript 代码实现空位补零,比如 pad(12, 3) => 012之类的。这里介绍四种javascript的方法,顺便也给出PHP的方法。

计算机算法

不使用递归如何求裴波那契数列

用函数求解裴波那契数列
裴波那契数列 1,1,2,3,5,8,13,21…………,一般来说使用递归会使问题简单很多。但是有些时候会要求我们不用递归解决这类问题,比如Lisp这种不支持递归的语言,或者对程序的执行效率要求很高,或者面试等等场合。本文给出一种不使用递归求解裴波那契数列的方案。
1 / 2 首页 < Prev 1 2 Next > 尾页 页码: