开发者社区> 苟哥> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

正确看待递归函数

简介: 实际编码过程中,我觉得尽量少用,而是使用for或while去替代它,这样会让你少走很多弯路。​
+关注继续查看

什么是递归函数

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

递归函数的作用

  • 可以执行for或while语句相同的任务
  • 有些情况可以少写代码,让代码看起来更简练
    举一个例子,数学中我们有学习过求一个正整数的阶乘。阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积。我们使用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
//用两个方法实现将一个字符串逆置
​
//递归实现
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是如何被执行的:
_
上图中,右侧带数字的向下箭头表示程序实际运行的代码顺序。被不同颜色的线连接的表示一个完整的函数体(因为我们刚刚说了遇到子函数后并不是停止运行函数后面的代码,而是保存现场,去执行子函数,执行完恢复现场接着执行),因此reverse_r('hello')虽然是最先被执行的,但是它的后一句代码echo substr('hello', 0, 1) 却是最后才被执行的。最后得到的打印效果也就实现了将字符串逆置,但是用递归这个方式确实不容易被理解啊。

应该使用递归函数吗

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
1021 个位数统计 (15 分)
给定一个 k 位整数 N=dk−1​10k−1+⋯+d1​101+d0​ (0≤di​≤9, i=0,⋯,k−1, dk−1​>0),请编写程序统计每种不同的个位数字出现的次数。例如:给定 N=100311,则有 2 个 0,3 个 1,和 1 个 3。
21 0
小六六学Zookeeper(三)(下)
前言 文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820… 种一棵树最好的时间是十年前,其次是现在
14 0
zookeeper技术分享
ZooKeeper是一个分布式的,开放源码的分布式应用程序协调服务,是Google的Chubby一个开源的实现。 ZooKeeper的目标就是封装好复杂易出错的关键服务,将简单易用的接口和性能高效、功能稳定的系统提供给用户。 ZooKeeper包含一个简单的原语集,提供Java和C的接口。 ZooKeeper代码版本中,提供了分布式独享锁、选举、队列的接口,代码在$zookeeper_home\src\recipes。其中分布锁和队列有Java和C两个版本,选举只有Java版本。
47 0
+关注
苟哥
脚踏实地,希望不被技术世界淘汰
26
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载