搜索
首页后端开发php教程PHP数据结构基础之递归

PHP数据结构基础之递归

Jul 07, 2018 pm 03:29 PM
递归递归调用

这篇文章主要介绍了关于PHP数据结构基础之递归,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下

什么是递归?

之前说到,递归是一种将大问题分解为小问题的解决方案。一般来说,递归被称为函数自身的调用。这么说可能听起来很奇怪,事实上在递归中,函数确实必须调用自己。

一个栗子

例如在数学中,我们都知道“阶乘”的概念。例如5的阶乘就是5*4*3*2*1

  • 5!= 5 * 4!

  • 4!= 4 * 3!

  • 3!= 3 * 2!

  • 2!= 2 * 1!

  • 1!= 1 * 0!

  • 0!= 1

我们可以总结出求n的阶乘的规律,即 n! = n * (n -1) !

这就体现了递归。你可以从中发现,我们把求5的阶乘一步一步转化成了另外一个个的小问题。

递归算法的特性

  • 每一个递归调用都必须基于一个小的子问题。例如5的阶乘就是5乘4的阶乘。

  • 递归必须有一个Base case。例如阶乘的Base case就是0,当条件是0的时候,就停止递归。

  • 递归中避免循环调用,否则最后计算机会显示栈溢出的错误。

function factorial(int $n): int
{
    if ($n = 0) {
        return 1;
    }
    
    return $n * factorial($n - 1);
}

看上面的代码,我们可以看到对于阶乘问题的解决方案我们有一个基础的条件就是当n为0的时候,我们返回1。如果不符合这个条件,我们返回nfactorial(n) ,这符合递归特性的第一条和第三条。我们避免了循环调用,因为我们把每一次的递归调用都分解成了大问题的一个小的子问题。上面的算法思想可以表达成:

递归Vs迭代clipboard.png

上面的递归代码我们同样可以使用迭代的方法实现

function factorial(int $n): int
{
    $result = 1;
    
    for ($i = $n; $i > 0; $i--) {
        $result*= $n;
    }
    
    return $result;
}

如果一个问题可以很容易的使用迭代来解决,我们为何要使用递归?

递归是用来处理更加复杂的问题的,不是所有的问题都可以简单的使用迭代来解决的。递归使用函数调用来管理调用栈,所以相比于迭代递归会使用更多和时间以及内存。此外,在迭代中,我们每一步都会有一个结果,但是在递归中我们必须等到base case执行结束才会有任何结果。看上面的例子,我们发现在递归算法中我们没有任何变量或者声明来保存结果,而在迭代算法中,我们每一次都用$result来保存了返回结果。

斐波那契数列

在数学中,斐波那契数列是一个特殊的整数数列,数列中的每一个数的是由另外两个数求和产生的。规则如下:

1016398047-5b2f6713f2bc9_articlex[1].png

function fibonacci($n)
{
    if ($n == 0) {
        return 0;
    }
    
    if ($n == 1) {
        return 1;
    }
    
    return fibonacci($n - 1) + fibonacci($ - 2);
}

最大公因数

另外一个使用递归算法的常见问题是求两个数的最大公因数。

2350312577-5b2f67141b9e5_articlex[1].png

function gcd(int $a, int $b)
{
    if ($b == 0) {
        return $a;
    }
    
    return gcd($b, $a % $b);
}

递归类型

  • 线性递归

在每一次递归调用中,函数只调用自己一次,这就叫做线性递归。

  • 二分递归

在二分递归中,每一次递归调用函数调用自己两次。求解斐波那契数列的算法就是二分递归,除此之外还有二分查找、分治算法、归并排序等也使用了二分递归。

  • 尾递归

当一个递归返回的时候没有等待的操作的时候就称为尾递归。斐波那契算法中,返回值需要乘以前一个递归的返回值,因此他不是尾递归,而求解最大公因式的算法是尾递归。尾递归是线性递归的一种形式。

  • 相互递归

例如在每一次递归调用中 有 A() 调用 B(), B() 调用 A() ,这样的递归就叫做相互递归。

  • 嵌套递归

当一个递归函数把自己作为一个参数进行递归调用时,就叫做嵌套递归。一个常见的栗子就是阿克曼函数,看下面的表达。

896880774-5b2f6713eb772_articlex[1].png

看最后一行的,可以看到第二个参数就是递归函数自己。

下一节

下一篇内容会使用递归解决一些实际开发中会遇到的问题,例如构建N级分类、构建嵌套评论、目录文件的遍历等等。

以上就是本文的全部内容,希望对大家的学习有所帮助,更多相关内容请关注PHP中文网!

相关推荐:

PHP获取客户端真实IP地址的方法

PHP中使用Elasticsearch的方法

以上是PHP数据结构基础之递归的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
PHP与Python:了解差异PHP与Python:了解差异Apr 11, 2025 am 12:15 AM

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

php:死亡还是简单地适应?php:死亡还是简单地适应?Apr 11, 2025 am 12:13 AM

PHP不是在消亡,而是在不断适应和进化。1)PHP从1994年起经历多次版本迭代,适应新技术趋势。2)目前广泛应用于电子商务、内容管理系统等领域。3)PHP8引入JIT编译器等功能,提升性能和现代化。4)使用OPcache和遵循PSR-12标准可优化性能和代码质量。

PHP的未来:改编和创新PHP的未来:改编和创新Apr 11, 2025 am 12:01 AM

PHP的未来将通过适应新技术趋势和引入创新特性来实现:1)适应云计算、容器化和微服务架构,支持Docker和Kubernetes;2)引入JIT编译器和枚举类型,提升性能和数据处理效率;3)持续优化性能和推广最佳实践。

您什么时候使用特质与PHP中的抽象类或接口?您什么时候使用特质与PHP中的抽象类或接口?Apr 10, 2025 am 09:39 AM

在PHP中,trait适用于需要方法复用但不适合使用继承的情况。1)trait允许在类中复用方法,避免多重继承复杂性。2)使用trait时需注意方法冲突,可通过insteadof和as关键字解决。3)应避免过度使用trait,保持其单一职责,以优化性能和提高代码可维护性。

什么是依赖性注入容器(DIC),为什么在PHP中使用一个?什么是依赖性注入容器(DIC),为什么在PHP中使用一个?Apr 10, 2025 am 09:38 AM

依赖注入容器(DIC)是一种管理和提供对象依赖关系的工具,用于PHP项目中。DIC的主要好处包括:1.解耦,使组件独立,代码易维护和测试;2.灵活性,易替换或修改依赖关系;3.可测试性,方便注入mock对象进行单元测试。

与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。Apr 10, 2025 am 09:37 AM

SplFixedArray在PHP中是一种固定大小的数组,适用于需要高性能和低内存使用量的场景。1)它在创建时需指定大小,避免动态调整带来的开销。2)基于C语言数组,直接操作内存,访问速度快。3)适合大规模数据处理和内存敏感环境,但需谨慎使用,因其大小固定。

PHP如何安全地上载文件?PHP如何安全地上载文件?Apr 10, 2025 am 09:37 AM

PHP通过$\_FILES变量处理文件上传,确保安全性的方法包括:1.检查上传错误,2.验证文件类型和大小,3.防止文件覆盖,4.移动文件到永久存储位置。

什么是无效的合并操作员(??)和无效分配运算符(?? =)?什么是无效的合并操作员(??)和无效分配运算符(?? =)?Apr 10, 2025 am 09:33 AM

JavaScript中处理空值可以使用NullCoalescingOperator(??)和NullCoalescingAssignmentOperator(??=)。1.??返回第一个非null或非undefined的操作数。2.??=将变量赋值为右操作数的值,但前提是该变量为null或undefined。这些操作符简化了代码逻辑,提高了可读性和性能。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能