简介PHP递归算法和应用

PHP作为开发动态页面WEB的首选技术，对于它的基础知识我们一定要牢记，这让才能有助于编程。我们一起来看看PHP递归算法是怎么回事吧。

1、调用子程序的含义：

当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，然后执行类似于BASIC语言的GOTO语句，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句（我这又忽略了返回值处理）子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句，主程序执行到结束。做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完（我这饭吃得也够累的了J）。

2、认识递归函数

我们在高中时都学过数学归纳法，PHP递归算法例如：

求 n！我们可以把n！这么定义也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序：

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span></span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用 factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次 factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（－1）。。。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成：

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (I</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>0) </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i; else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span>;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

3、如何考虑用PHP递归算法来解决问题

例：求s=1+2+3+4+5+6+……+n本来这个问题我们过去常用循环累加的方法。而这里如要用递归的方法，必须考虑两点：
1） 能否把问题转化成递归形式的描述；
2） 是否有递归结束的边界条件。

显然递归的两个条件都有了：

<ol class="dp-xml">
<li class="alt"><span><span>1） s(n) =s(n-1)+n  </span></span></li>
<li class=""><span>2） s(1)=1 </span></li>
</ol>

所以源程序为：

<ol class="dp-xml">
<li class="alt"><span><span>int progression(int n){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (</span><span class="attribute"><font color="#ff0000">n</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> )</span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">progression</font></span><span>(n-1)+n;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

4、递归的应用

中序遍历二叉树

<ol class="dp-xml">
<li class="alt"><span><span>void inorder (BinTree T){  </span></span></li>
<li class=""><span>if (T){  </span></li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>lchild);  </span>
</li>
<li class="">
<span>printf(“%c”,T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>data);  </span>
</li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>rchild);  </span>
</li>
<li class=""><span>}  </span></li>
<li class="alt"><span>} </span></li>
</ol>