搜索
首页后端开发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
C++ lambda 表达式是否支持递归?C++ lambda 表达式是否支持递归?Apr 17, 2024 pm 09:06 PM

是的,C++Lambda表达式可以通过使用std::function支持递归:使用std::function捕获Lambda表达式的引用。通过捕获的引用,Lambda表达式可以递归调用自身。

在Java中递归地计算子字符串出现的次数在Java中递归地计算子字符串出现的次数Sep 17, 2023 pm 07:49 PM

给定两个字符串str_1和str_2。目标是使用递归过程计算字符串str1中子字符串str2的出现次数。递归函数是在其定义中调用自身的函数。如果str1是"Iknowthatyouknowthatiknow",str2是"know"出现次数为-3让我们通过示例来理解。例如输入str1="TPisTPareTPamTP",str2="TP";输出Countofoccurrencesofasubstringrecursi

递归程序在C++中找到数组的最小和最大元素递归程序在C++中找到数组的最小和最大元素Aug 31, 2023 pm 07:37 PM

我们以整数数组Arr[]作为输入。目标是使用递归方法在数组中找到最大和最小的元素。由于我们使用递归,我们将遍历整个数组,直到达到长度=1,然后返回A[0],这形成了基本情况。否则,将当前元素与当前最小或最大值进行比较,并通过递归更新其值以供后续元素使用。让我们看看这个的各种输入输出场景−输入 −Arr={12,67,99,76,32};输出 −数组中的最大值:99解释 &mi

如何解决Python的最大递归深度错误?如何解决Python的最大递归深度错误?Jun 24, 2023 pm 02:48 PM

Python是一门易学易用的编程语言,然而在使用Python编写递归函数时,可能会遇到递归深度过大的错误,这时就需要解决这个问题。本文将为您介绍如何解决Python的最大递归深度错误。1.了解递归深度递归深度是指递归函数嵌套的层数。在Python默认情况下,递归深度的限制是1000,如果递归的层数超过这个限制,系统就会报错。这种报错通常称为“最大递归深度错误

如何使用Vue表单处理实现表单的递归嵌套如何使用Vue表单处理实现表单的递归嵌套Aug 11, 2023 pm 04:57 PM

如何使用Vue表单处理实现表单的递归嵌套引言:随着前端数据处理和表单处理的复杂性不断增加,我们需要通过一种灵活的方式来处理复杂的表单。Vue作为一种流行的JavaScript框架,为我们提供了许多强大的工具和特性来处理表单的递归嵌套。本文将向大家介绍如何使用Vue来处理这种复杂的表单,并附上代码示例。一、表单的递归嵌套在某些场景下,我们可能需要处理递归嵌套的

如何在Linux中使用递归“ls”如何在Linux中使用递归“ls”Mar 20, 2024 am 10:03 AM

在Linux系统中,“ls”命令是一个非常有用的工具,它提供了对当前目录中文件和文件夹的简洁概述。通过“ls”命令,您可以快速查看文件和文件夹的权限、属性等重要信息。虽然“ls”命令是一个基本的命令,但是通过结合不同的子命令和选项,它可以成为系统管理员和用户的重要工具。通过熟练使用“ls”命令及其各种选项,您可以更高效地管理文件系统,快速定位所需文件,以及执行各种操作。因此,“ls”命令不仅可以帮助您了解当前目录结构,还可以提高您的工作效率。比如,在Linux系统中,通过使用带有递归选项的"ls

Go语言中的循环和递归的比较研究Go语言中的循环和递归的比较研究Jun 01, 2023 am 09:23 AM

注:本文以Go语言的角度来比较研究循环和递归。在编写程序时,经常会遇到需要对一系列数据或操作进行重复处理的情况。为了实现这一点,我们需要使用循环或递归。循环和递归都是常用的处理方式,但在实际应用中,它们各有优缺点,因此在选择使用哪种方法时需要考虑实际情况。本文将对Go语言中的循环和递归进行比较研究。一、循环循环是一种重复执行某段代码的机制。Go语言中主要有三

利用ThinkPHP6实现递归树结构利用ThinkPHP6实现递归树结构Jun 20, 2023 pm 02:48 PM

随着互联网的发展,各种网站和应用程序中都出现了树形结构的展示,例如分类目录、人员组织架构、权限管理等。在这些应用场景中,递归树结构已经成为了非常重要且实用的模型之一。ThinkPHP6是一种基于MVC模型的PHP开发框架,其拥有丰富的扩展库和优秀的性能,广受开发者的认可和使用,而在ThinkPHP6中实现递归树结构也变得更加方便了。下面,我们将介绍如何在Th

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.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。