交通银行网站开发,如何用代码制作网站,自己做网页,wordpress 中国提速递归的定义 递归#xff08;http:/en.wikipedia.org/wiki/Recursive#xff09;是一种函数调用自身#xff08;直接或间接#xff09;的一种机制#xff0c;这种强大的思想可以把某些复杂的概念变得极为简单。在计算机科学之外#xff0c;尤其是在数学中#xff0c;递归…递归的定义 递归http:/en.wikipedia.org/wiki/Recursive是一种函数调用自身直接或间接的一种机制这种强大的思想可以把某些复杂的概念变得极为简单。在计算机科学之外尤其是在数学中递归的概念屡见不鲜。例如最常用于递归讲解的斐波那契数列便是一个极为典型的例子而其他的例如阶层n!也可以转化为递归的定义n! n*(n-1)!.即使是在现实生活中递归的思想也是随处可见例如由于学业问题你需要校长盖章然而校长却说“只有教导主任盖章了我才会盖章”当你找到教导主任教导主任又说“只有系主任盖章了我才会盖章”...直到你最终找到班主任在得到班主任豪爽的盖章之后你要依次返回到系主任、教导主任、最后得到校长的盖章过程如下 盖章的故事虽然索然无味谁的大学生活没有点悲催的事情呢不悲催怎么证明我们年轻过但却很好的体现了递归的基本思想也就是递归的两个基本条件 1. 递归的退出条件这是递归能够正常执行的必要条件也是保证递归能够正确返回的必要条件。如果缺乏这个条件递归就会无限进行下去直到系统给予的资源耗尽在大多数语言中都是堆栈空间耗尽因此如果你在编程中碰到类似“stack overflow”(C语言中即栈溢出)和“max nest level of 100 reached”php中超出递归限制等错误多半是没有正确的退出条件导致了递归深度过大或者无限递归。 2. 递推过程。由一层函数调用进入下一层函数调用的递推。以n!为例。在n1的情况下。N! N*(N-1)! 便是该递归函数的递推过程我们也可以简单的称为“递归公式”。
有了这两个基本条件我们便得到了递归的一般模式, 用代码可以描述为
function Recur( param ){ if( reach the baseCondition ){ Calu();//计算 return ; } //else just do it recursively param modify(param)/修改参数准备进入下层调用 Recur(param);}
有了递归的一般模式我们便可以轻松实现大多的递归函数。例如:经常提起的斐波那契数列的递归实现再如目录的递归访问
function ScanDir($path){ if(is_dir($path)){ $handler opendir($path); while($dir readdir($handler)){ if($dir . || $dir ..){ continue; } if(is_dir($path./.$dir)){ ScanDir($path./.$dir./); }else{ echo file: .$path./.$dir.PHP_EOL; } } }}ScanDir(./);
细心的同学可能发现我们在表述的过程中多次使用“层”这个术语。主要有两大原因
1. 人们在分析递归的过程中经常使用递归树的形式来分析递归函数的走向。以斐波那契数列为例首先斐波那契数列的定义为 因此为了得到Fabn的值我们常常需要展开为“递归树”的形式如下图所示 而递归的计算过程则是从上而下从左而右一旦到达递归树的叶子节点也就是递归的退出条件便又层层向上返回。如下图所示引用网址http:/www.csharpwin.com/csharpspace/12292r4006.shtml: 2. 堆栈的结构。
跟递归有关的另一个重要的概念是栈借用百度百科中关于栈的解释“在Windows下,栈是向低地址扩展的数据结构是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的在 WINDOWS下栈的大小是2M也有的说是1M总之是一个编译时就确定的常数如果申请的空间超过栈的剩余空间时将提示overflow。因此能从栈获得的空间较小。” 在linux系统中也可以通过ulimit –s命令查看系统的最大栈大小。栈的特点是“后进先出”也就是最后压入的元素有最高的优先权每次压入数据时栈层层向上叠放而取数据时则是从栈顶取出需要的数据。正是由于栈的这一特性使得栈特别适合用于递归。具体来说在递归程序运行时系统会分配额定大小的栈空间每次函数调用的参数、局部变量、函数返回地址称为一个栈帧都会被压入到栈空间中称为“保护现场”以便在合适的时候“返回现场”每次该层的递归调用结束后便无条件由于无条件使栈溢出攻击称为可能可参考(http:/wenku.baidu.com/view/7fb00bc2d5bbfd0a7956737d.html 返回到之前保存的返回地址处继续执行代码。这样层层下来栈的结构恰似一叠有规律的盘子 作为递归的基本实例以下可用于练习 1. 目录的递归遍历。
2. 无限分类。
3. 二分查找和合并排序。
4. PHP内置的与递归行为有关的函数如array_merge_recursive,array_walk_recursive,array_replace_recursive等考虑它们的实现 理解递归-函数调用的堆栈跟踪 在c语言中可以通过GDB等调试工具跟踪函数调用的堆栈从而细致追踪函数的运行过程(关于GDB的使用推荐左耳朵耗子之前的博客http:/blog.csdn.net/haoel/article/details/2879 )。
而在php中可以使用的调试方法有
1.原生的print ,echo ,var_dump,print_r等通常对于较为简单的程序只需要在函数的 关键点输出即可。
2.Php内置的堆栈跟踪函数debug_backtrace 和debug_print_backtrace.
3.xdebug 和xhprof等调试工具。
为了方便理解还是以斐波那契数列为例这里我们假设n一定是非负数
function fab($n){debug_print_backtrace();if($n 1 || $n 0){return $n;}return fab($n - 1) fab($n - 2);}fab(4); 打印出的斐波那契的调用堆栈是
#0 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(3) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(3) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(1) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(3) called at [/search/nginx/html/test/Fab.php:8]
#3 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(0) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(3) called at [/search/nginx/html/test/Fab.php:8]
#3 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(1) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(3) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(1) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:10]
#0 fab(0) called at [/search/nginx/html/test/Fab.php:8]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:8]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:10] 初看这一堆乱七八糟的输出似乎毫无头绪。其实对于上述的每一行输出都包含如下几项内容
A. 所在的栈层次如#0表示是栈顶#1表示第一层栈帧#2表示第二层栈帧依次类推数字越大表示所在的栈帧深度越大。
B. 调用的函数和参数。如fab(4)表示实际的执行函数是fab函数4表示函数的实参。
C. 调用的位置包括文件名和执行的行数。
实际上我们加上一些额外的输出信息便可以更加清晰的看到函数的调用堆栈和计算过程例如我们加上函数层次的基本信息 function fab($n){ echo “-- n $n ----------------------------”.PHP_EOL;debug_print_backtrace();if($n 1 || $n 0){return $n;}return fab($n - 1) fab($n - 2);}fab(4)
则执行fab(4)之后的调用堆栈为
---- n 4 ---------------------------------------------
#0 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 3 ---------------------------------------------
#0 fab(3) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 2 ---------------------------------------------
#0 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(3) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 1 ---------------------------------------------
#0 fab(1) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(3) called at [/search/nginx/html/test/Fab.php:9]
#3 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 0 ---------------------------------------------
#0 fab(0) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(3) called at [/search/nginx/html/test/Fab.php:9]
#3 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 1 ---------------------------------------------
#0 fab(1) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(3) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 2 ---------------------------------------------
#0 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 1 ---------------------------------------------
#0 fab(1) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:11]
---- n 0 ---------------------------------------------
#0 fab(0) called at [/search/nginx/html/test/Fab.php:9]
#1 fab(2) called at [/search/nginx/html/test/Fab.php:9]
#2 fab(4) called at [/search/nginx/html/test/Fab.php:11] 对该输出的解释注意输出的前两列)由于程序需要计算fab(4)的值。而fab(4)的值依赖于fab(3)和fab(2)的值因而无法直接计算fab(4)的值需要将其压入栈中对应下图中的1。fab(4)的左分支为fab(3),而fab(3)的值也无法直接计算因而需要将fab(3)也压入栈中对应下图中的2同理fab(2)也需要压入栈中直到递归树的叶子节点。计算完叶子节点后依次退栈直到栈为空如下图所示 性能表现-递归效率分析 昨天在翻阅朴灵的《深入浅出NODE.js》的时候看到作者对不同的语言做性能测试时给出的测试结果。大致是通过简单的斐波那契数列的递归计算测试不同语言的计算时间从而大致评估不同语言的计算性能。其中PHP的计算时间让我极为吃惊在n40的情况下PHP计算斐波那契数列的耗时为1m17.728s也就是77.728s,与c语言的0.202s相比足足差了约380倍测试结果可见下图 我们知道PHP代码的执行过程是经过扫描代码、词法分析、语法分析等过程将PHP程序编译成中间代码Opcode字节码然后由zend核心引擎负责执行因而从本质上说PHP是封装在C语言基础上的一个高级语言实现。这样由于PHP编译过程并没有做过多的编译优化加之需要在Zend虚拟机上运行效率与原生C语言相比必然要大打折扣但是居然会有如此大的差距还是难免让人匪夷所思。
PHP中递归的效率为何如此低下其中一个需要知道的是PHP中不支持尾递归优化这样会导致树形递归的反复迭代和重复计算因而递归的效率大大下降能够容忍的递归层次也大大降低。在c/c中使用gcc -O2等级以上的编译时编译会对递归做相应的优化在这篇文章PHP函数的实现原理及性能分析中,作者的一个解释是“函数递归是通过堆栈来完成的。在php中也是利用类似的方法来实现。Zend为每个php函数分配了一个活动符号表(active_sym_table)记录当前函数中所有局部变量的状态。所有的符号表通过堆栈的形式来维护每当有函数调用的时候分配一个新的符号表并入栈。 当调用结束后当前符号表出栈。由此实现了状态的保存和递归。 对于栈的维护zend在这里做了优化。预先分配一个长度为N的静态数组来模拟堆栈这种通过静态数组来模拟动态数据结构的手法在我们自己的程序中也经常有使用这种方式避免了每次调用带来的内存分配、销毁。ZEND只是在函数调用结束时将当前栈顶的符号表数据clean掉即可。因为静态数组长度为N一旦函数调用层次超过N程序不会出现栈溢出这种情况下zend就会进行符号表的分配、销毁因此会导致性能下降很多。在zend里面N目前取值是32。因此我们编写php程序的时候函数调用层次最好不要超过32。” 另外php bug中也有说明“PHP 4.0 (Zend) uses the stack for intensive data, rather than using the heap. That means that its tolerance recursive functions is significantly
lower than that of other languages ”
SO, 在PHP中如果不是非常必要我们建议最好尽量少使用递归尤其是在递归层次较大或者无法估算递归的层次时。
参考文献
1. http://www.csharpwin.com/csharpspace/12292r4006.shtml
2. http:/devzone.zend.com/283/recursion-in-php-tapping-unharnessed-power/
3. http://blog.csdn.net/heiyeshuwu/article/details/5840025
4. http:/www.nowamagic.net/librarys/veda/detail/2336
5. http://www.cnblogs.com/JeffreyZhao/archive/2009/03/26/tail-recursion-and-continuation.html
6. http://wenku.baidu.com/view/7fb00bc2d5bbfd0a7956737d.html
