php递归函数 php递归算法经典实例大全

递归函数是数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0),射影函数,后继函数S(x)=x+1,它们合称初始函数。要想由旧函数作出新函数,必须使用各种算子。在数理逻辑和计算机科学中,递归函数或μ-递归函数是一类从自然数到自然数的函数,它是在某种直觉意义上是"可计算的"。事实上,在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。

 

递归函数

数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数,未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数递归函数;后继函数S(x)=x+1。它们合称初始函数。要想由旧函数作出新函数,必须使用各种算子。
代入(又名复合或叠置)是最简单又最重要的造新函数的算子,其一般形状是:由一个m元函数ƒ与m个n元函数 g1,g2,…,gm 造成新函数 ƒ (g1(x1,x2,…,xn),g2(x1,x2,…,xn),…,gm(x1,x2,…,xn)),亦可记为ƒ(g1g2,…,gm)(x1x2,…,xn)。另一个造新函数的算子是原始递归式。具有n个参数u1u2,…,un的原始递归式为:

递归函数

具有一个参数的原始递归式可简写为:

递归函数

其特点是,不能由gh两函数直接计算新函数的一般值ƒ(u,x),而只能依次计算ƒ(u,0),ƒ(u,1),ƒ(u,2),…;但只要依次计算,必能把任何一个ƒ(u,x)值都算出来。换句话说只要g,h为全函数且可计算,则新函数f也是全函数且可计算。
由初始函数出发,经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算,故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数,可见原始递归函数是包括很广的。但是W.阿克曼证明了,可以作出一个可计算的全函数,它不是原始递归的。经过后人改进后,这个函数可写为如下定义的阿克曼函数:

递归函数

容易看出,这个函数是处处可计算的。任给m,n的值,如果m为0,可由第一式算出;如果m不为0而n为0,可由第二式化归为求g(m,1)的值,这时第一变目减少了;如果m,n均不为0,根据第三式可先计算g(m,n-1),设为α,再计算g(m-1,α),前者第二变目减少(第一变目不变),后者第一变目减少。极易用归纳法证得,这样一步一步地化归,最后必然化归到第一变目为0,从而可用第一式计算。所以这个函数是处处可计算的。此外又容易证明,对任何一个一元原始递归函数ƒ(x),永远可找出一数α使得ƒ(x)<g(α,x)。这样,g(x,x)+1便不是原始递归函数,否则将可找出一数b使得g(x,x)+1<g(b,x)。令x=b,即得g(b,b)+1<g(b,b),而这是不可能的。
另一个重要的造新函数的算子是造逆函数的算子,例如,由加法而造减法,由乘法造除法等。一般,设已有函数ƒ(u,x),就x解方程ƒ(u,x)=t,可得x=g(u,t)。这时函数g叫做ƒ的逆函数。至于解一般方程ƒ(ut,x)=0而得xg(ut)可以看作求逆函数的推广。解方程可以看作使用求根算子。ƒ(u,tx)=0的最小x根(如果有根的话),记为μxƒ(u,t,x)=0】。当方程没有根时,则认为μxƒ(u,t,x)=0】没有定义。可见,即使ƒ(u,t,x)处处有定义且可计算,但使用求根算子后所得的函数μxƒ(u,t,x)=0】仍不是全函数,可为部分函数。但只要它有定义,那就必然可以计算。这算子称为μ算子。如果ƒ(u,t,x)本身便是部分函数,则 μxƒ(u,t,x)=0】的意义是:当ƒ(u,t,n)可计算且其值为0,而x<nƒ(u,t,x)均可计算而其值非0,则 μxƒ(u,t,x)=0】指n;其他情况则作为无定义。例如,如果ƒ(u,t,x)=0根本没有根,或者虽然知道有一根为n,但ƒ(u,t,n-1)不可计算,那么 μxƒ(u,t,x)=0】都作为没有定义。在这样定义后,只要 μxƒ(u,t,x)=0】有值便必可计算。由初始函数出发,经过有穷次使用代入、原始递归式与 μ算子而作成的函数叫做部分递归函数,处处有定义的部分递归函数称为全递归函数,或一般递归函数。
原始递归函数类里还有一个重要的子类称为初等函数类,它是由非负整数与变元经过有穷次加、算术减(即|α-b|)、乘、算术除递归函数、叠加Σ、叠乘П而得的函数组成的类。
波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类,称为格热高契克分层或波兰分层。
要把递归函数应用于谓词,首先要定义谓词的特征函数。谓词R(x,y)的特征函数是

递归函数

称谓词R 是递归谓词,若R 的特征函数是递归函数;称自然数子集A为递归集,若谓词xA是递归谓词。有了上述定义,就可以用递归函数来处理递归谓词和递归集。为了处理N×N(其中N 为自然数集)的子集,就要建立配对函数,所谓配对函数通常是指由N×NN 的一个函数ƒ(xy)与它的逆函数g1(z),g2(z)。它们都满足以下关系。

一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。这对于程序员来说,通常有很高的实用价值,常用来将复杂的问题分解为简单的并相同的情况,反复做这种处理直到问题解决。

用递归函数与不用递归函数的区别

示例一:使用静态变量

1
2
3
4
5
6
7
8
function test(){
  static $dig=0;
  if($dig++<10){
    echo $dig;
    test();
  }
}
test();//12345678910

示例二:使用递归函数和循环实现字符串逆转排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function unreverse($str){
  for($i=1;$i<=strlen($str);$i++){
    echo substr($str,-$i,1);
  }
}
unreverse("abcdefg");//gfedcbc
function reverse($str){
  if(strlen($str)>0){
    reverse(substr($str,1));
    echo substr($str,0,1);
    return;
  }
}
reverse("abcdefg");//gfedcbc

递归函数很多时候我们可以循环替代,建议当我们不能用循环替代时再用,因为用循环我们更容易理解,更不容易出错。

php递归函数 php支付递归函数,递归函数就是调用自己本身,这些函数特别适用于浏览动态数据结构,例如树和列表。
几乎没有web应用程序要求使用复杂的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
function reversr_r($str)
{
if (strlen($str)>0)
reverse_r(substr($str,1));
echo substr($str,0,1);
return;
}
?>
<?php
function reverse_i($str)
{
for($i=1;$i<=strlen($str);$i++)
{
echo substr($str,-$i,1);
}
}

这个程序清单中实现两个函数,这两个函数都可以相反的顺序打印字符串的内容


函数reversr_r是通过递归实现的,而函数reverse_i()是通过循环实现的

 

递归函数即自调用函数,在函数体内部直接或者间接的自己调用自己,即函数的嵌套调用是函数本身。通常在此类型的函数提之中会附加一个条件判断叙述,以判断是否需要执行递归调用,并且在特定的条件下终止函数的递归调用动作,把目前流程的主控权交回到上一层函数来执行。以此,当某个执行递归调用的函数没有附加条件判断叙述时,可能会造成无限循环的错误情形。

函数递归调用最大的好处在于可以精简程序中的复杂重复调用程序,并且能以这种特性来执行一些较为复杂的运算动作。例如,列表、动态树形菜单及遍历目录等操作。相应的非递归函数虽然效率高,但却比较难编程,而且相对来说可读性差。现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高,程序在更多的场合优先考虑可读而不是高效,所以,鼓励用递归函数实现程序思想。

一个简单的递归调用实例如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
<?php
 //声明一个函数,用于测试递归
 function test($n){
   echo $n."&nbsp;";        //在函数开始输出参数的值
   if($n>0){                //判断参数是否大于0
     test($n-1);            //如果参数大于0则调用自己,并将参数减1后再次传入
   }else{                   //判断参数是不大于0
     echo "<-------->  ";
   }
   echo $n."&nbsp;";
 }
 test(10);                   //调用test函数将整数10传给参数
?>

该程序执行后输出如下的结果:

1
10 9 8 7 6 5 4 3 2 1 0 <--------> 0 1 2 3 4 5 6 7 8 9 10

找到结果中后半部分的数字正向顺序输出的原因

说明:在上面的实例中声明了一个 test()函数,该函数需要一个整型的参数。在函数外面通过传递整数 10 作为参数调用 test()函数。在 test()函数体中,第一条代码输出参数的值和一个空格。然后判断条件是否成立,成立则调用自己并将参数减 1 再次传入。开始调用时,它是外层调内层,内层调更内一层,直到最内层由于条件不允许必须结束。最内存结束了,输出 <--------> 作为分界符,执行调用之后的代码输出参数的值和空格,它就会回到稍外一层继续执行。稍外一层在结束时,退回到在稍外一层继续执行,层层推出,直到最外层结束。执行完成以后的结果就是我们上面看到的结果。

树型菜单在很多桌面应用系统中都有非常广泛的应用,其主要优点是结构清晰,利于使用者非常清楚的知道目前自己所在的位置。但在web上树型菜单的应用因为没有理想的现成组件可以拿过来直接使用,所以一般的情况下,程序员主要是通过JavaScript来实现一些简单的树型结构菜单,但这些菜单往往都是事先定好各菜单项目,以及各菜单项目之间的层次关系,不利于扩充,一旦需要另一个菜单结构时,往往还需要重新编写,因此使用起来不是很方便。

    经过对函数递归的研究,我发现这种树型菜单可以通过递归函数,使树型菜单的显示实现动态变化,并没有级数的限制。下面就是我用php,MySQL,JavaScript写的一个动态树型菜单的处理代码,如果大家有兴趣的话,就和我一起来看看我是如何实现的吧:)

    首先,我们需要一个数据库,在这个数据库中,我们建立以下一张表:

CREATE TABLE menu (
id tinyint(4) NOT NULL auto_increment,
parent_id tinyint(4) DEFAULT \\'0\\' NOT NULL,
name varchar(20),
url varchar(60),
PRIMARY KEY (id)
);


    这张表中
    id 为索引
    parent_id 用来保存上一级菜单的id号,如果是一级菜单则为0
    name 为菜单的名称,也就是要在页面上显示的菜单内容
    url 如果某菜单为末级菜单,则需要指定该连接的url地址,这个字段就是用来保存此地址的,其他非末级菜单,该字段为空

更多
  • 该日志由 于2017年12月16日发表在 未分类 分类下, 你可以发表评论,并在保留原文地址 及作者的情况下引用到你的网站或博客。
  • 本文链接: php递归函数 php递归算法经典实例大全 | 帮助信息-动天数据
  • 文章标签:
  • 版权所有: 帮助信息-动天数据-转载请标明出处
  • 【上一篇】 【下一篇】

    0 Comments.