正确看待递归函数

苟哥 2019-07-19 AM 1424℃ 0条

#### 什么是递归函数
我们都知道基本上的编程语言都支持在一个函数中调用其他的函数。如果这个函数在内部调用它自己，那么我们就称这个函数为递归函数。

------

#### 递归函数的作用

- 可以执行for或while语句相同的任务
- 有些情况可以少写代码，让代码看起来更简练

举一个例子，数学中我们有学习过求一个正整数的**阶乘。**阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于 1808 年发明的运算符号，是数学术语。一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积。我们使用PHP语言用两种方法实现阶乘的运算，代码如下：

```PHP
<?php

//使用递归的方式
function factorial_1($n){
  return $n == 1 ? 1 : $n * factorial($n - 1);
}
//使用while的方式
function factorial_2($n){
  $res = 1;
  while ($n > 1) {
    $res = $res * $n--;
  }
  return $res;
}
$n = 5;
echo "使用阶乘的方式：" . factorial_1($n) . "<br>";
echo "使用while的方式： " . factorial_2($n) . "<br>";
 ```

打开浏览器运行该脚本，可以得到相同的结果。观察两个函数的实现，不难发现使用阶乘的方式，代码量看起来似乎是少一些，但是也没有特别明显。

------

#### 递归函数的弊端

- 性能低于for和while,同时会占用更高的内存
- 如果不设置递归的边界，那么就会造成死循环，直接将服务器跑崩
- 虽然可以替代for和while的实现，但是有些情况使用递归会显得很难理解。这边举个例子（当时也是困扰苟哥我许久啊），代码实现如下：

```PHP
<?php
//用两个方法实现将一个字符串逆置

//递归实现
function reverse_r($str) { 
  if (strlen($str)>0) {
    reverse_r(substr($str, 1)); 
  }
  echo substr($str, 0, 1);
  return; 
}

//for循环实现
function reverse_i($str) {
  for ($i=1; $i<=strlen($str); $i++) {
    echo substr($str, -$i, 1); 
  }
  return; 
}

reverse_r('Hello'); 
echo '<br />'; 
reverse_i('Hello');
```

虽然两个方法得到的结果是一样的，但是明显reverse_i这个方式是更好理解的，直接从字符串的最后一个位置开始逐个打印字符。而分析reverse_r这个方法，你会发现不是很好理解，如果你之前不知道一个事实——“函数内，当遇到子函数后并不是停止运行函数后面的代码，而是保存现场，去执行子函数，执行完恢复现场接着执行”，那么我猜你一定很难理解程序是怎么实现字符串逆置的。什么意思呢？就是reverse_i脚本的第9行那句代码会执行n次（n表示递归次数），但是每次执行的顺序刚好是和函数的循环顺序相反的，我们借助下图来理解reverse_i是如何被执行的：

![递归.png](http://images.kuryun.com/blog/typecho/递归.png)

上图中，右侧带数字的向下箭头表示程序实际运行的代码顺序。被不同颜色的线连接的表示一个完整的函数体（因为我们刚刚说了遇到子函数后并不是停止运行函数后面的代码，而是保存现场，去执行子函数，执行完恢复现场接着执行），因此reverse_r('hello')虽然是最先被执行的，但是它的后一句代码echo substr('hello', 0, 1) 却是最后才被执行的。最后得到的打印效果也就实现了将字符串逆置，但是用递归这个方式确实不容易被理解啊。

------

#### 编应该使用递归函数吗

从知识点全面性的角度，我觉得可以也应该去学习递归思想。但是在实际编码过程中，我觉得尽量少用，而是使用for或while去替代它，这样会让你少走很多弯路。

标签: 算法, 递归函数, PHP

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：http://www.i366211.com/archives/54/

上一篇 C程序设计语言第2版习题4-1

下一篇配置MySQL主从复制

正确看待递归函数

评论啦~

栏目分类

标签云

友情链接申请

正确看待递归函数

 评论啦~

 栏目分类

标签云

友情链接申请

评论啦~

栏目分类

标签云

友情链接申请