データ構造とアルゴリズム 再帰的アルゴリズム C++ および PHP の実装

递归算法：就是一种直接或间接调用自身的算法。

实现过程：通过函数或者子过程来完成，在函数或者子过程中编写代码直接或间接的调用自己，即可完成递归操作。（相同类别的问题，把问题层层转换为规模缩小的子问题到最小问题有 已知条件，然后 来求解，然后得到结果逐级返回。其实也是一种循环。）

最主要体现： 小的代码量解决了非常复杂的问题

特点：

1、递归就是方法里调用自身

2、必须有一个明确的递归结束条件，称为递归出口。

3、简洁但是运行效率较低，一般不提倡使用

4、每一层的返回点、局部变量等开辟了栈来存储，递归次数过多容易造成栈溢出。

实例1：求阶乘

C++代码：

#include<iostream>int factorial(int n);int main(){    using namespace std;    int n;    cout << "请输入一个数字:";    cin >> n;    cout << n << "的阶乘为: " << factorial(n) <<endl;    return 0;}int factorial(int n){    if (n == 1)        return 1;    return n*factorial(n-1);}

运行结果：

实例2：数制转换

代码：

#include<iostream>#include<cstring>void feelTheBase(char *s, int n, int sys);int main(){    using namespace std;    char s[60];    int n,sys;    cout << "请输入一个整数:";    cin >> n;    cout << "请输入要转换的进制类型(2,8,16):";    cin >> sys;    feelTheBase(s, n, sys);    cout << n << "转换成" << sys << "进制结果为: " << s <<endl;    return 0;}void feelTheBase(char *s, int n, int sys){    char bit[] = {"0123456789ABCDEF"};    int len;    if (n == 0)    {        strcpy(s, "");        return;    }    feelTheBase(s, n/sys, sys);    len = strlen(s);    s[len] = bit[n%sys];    s[len+1] = '\0';}

运行结果：

实例3： 列出某个目录下所有的子目录和文件（还可以用 scandir函数更方便 ）

PHP实现代码：

<?phpfunction rec($dir, $lev=0){    $dh = opendir($dir); while (($file = readdir($dh)) != false) {  if ($file == '.' || $file == '..') {   continue;  }  if (is_dir($dir.'/'.$file)){      $arr = explode("/",$dir.'/'.$file);   $lev = count($arr)-3;      echo str_pad('',$lev, "--")."目录".$file."<br/>";   rec($dir.'/'.$file, $lev+1);  }else {   echo str_pad('',$lev, "--").$file."<br/>";     } }  closedir($dh);}$dir = "./";rec($dir);?>

运行结果：