当前位置:

首页 > 编程开发 > PHP如何实现斐波那契数列递归_PHP实现斐波那契数列递归方法【算法】

PHP如何实现斐波那契数列递归_PHP实现斐波那契数列递归方法【算法】

PhpStorm macOS版
PhpStorm macOS版

PhpStorm 是 JetBrains 推出的专业 PHP 集成开发环境,可在 Mac 上完成代码编写、智能检查、重构、调试、测试和数据库管理。它支持主流 PHP 框架、Composer、Git、Docker 与远程解释器。

立即下载
¥890
Mac 2026-10-13
数据库 编程开发 phpstorm 服务器管理 集成开发环境

PHP递归实现斐波那契数列有四种方法:基础递归直接按定义计算,但重复计算多;记忆化递归用缓存优化,时间复杂度降至O(n);尾递归风格通过参数传递累计值;递归构建数组可生成前n项完整序列。

本文目录

    PHP 递归实现斐波那契数列:四种方法详解

    在 PHP 里用递归生成斐波那契数列,其实是个非常经典的练手场景。斐波那契数列的定义大家应该都熟悉:F(0)=0,F(1)=1,之后的每一项都是前两项之和。如果要用递归来实现,那核心就是让函数不断调用自身,直到触底。下面整理了四种常见的递归写法,从最基础的到带优化的,再到生成完整数组的,你可以根据实际需求来选。

    PHP如何实现斐波那契数列递归_PHP实现斐波那契数列递归方法【算法】

    一、基础递归实现

    这是最直接的方法,严格照着数学定义来:F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)(n≥2)。每次调用都会拆成两个更小的子问题,直到递归到底。

    具体步骤是这样的:

    • 创建一个函数 fibonacci($n),接收一个整数参数。
    • 在函数里判断:如果 $n 等于 0,直接返回 0;如果 $n 等于 1,返回 1。
    • 否则,返回 fibonacci($n - 1) + fibonacci($n - 2)。
    • 调用 fibonacci(10) 就能得到第10项(从0开始计数)的值 55。

    这种方法虽然简单,但有个明显的硬伤:重复计算太多,时间复杂度是 O(2ⁿ),n 稍微大一点就慢得离谱。

    二、带记忆化的递归实现

    既然基础递归有大量重复计算,那最简单的优化就是把算过的结果存起来,下次直接取。用 PHP 的静态数组就能搞定。

    做法如下:

    • 在函数内部声明 static $cache = [],用来存储已经计算过的项。
    • 每次调用时先检查 $n 是否已经在 $cache 里,如果是,直接返回 $cache[$n]。
    • 如果没缓存,就按基础递归的逻辑计算结果,然后把结果存到 $cache[$n] 里。
    • 最后返回 $cache[$n] 的值。

    这样一来,每个 n 只计算一次,效率大大提升,时间复杂度降到 O(n)。

    三、尾递归风格实现(模拟)

    PHP 本身并不支持尾递归优化,但我们可以在写法上模拟尾递归:通过额外参数传递累计值,让递归调用出现在函数的末尾。这样逻辑更清晰,也方便人工追踪执行路径。

    具体实现:

    • 定义函数 fibonacci_tail($n, $a = 0, $b = 1),其中 $a 对应 F(0),$b 对应 F(1)。
    • 当 $n 等于 0 时,返回 $a;当 $n 等于 1 时,返回 $b。
    • 否则,递归调用 fibonacci_tail($n - 1, $b, $a + $b)。
    • 调用 fibonacci_tail(10, 0, 1) 得到结果 55。

    这种写法虽然没有性能上的优化(因为 PHP 不会帮你做尾递归消除),但逻辑上更接近迭代,写起来也舒服。

    四、递归生成指定长度数列数组

    前面的方法都只返回单个数值,有时候我们需要直接输出前 n 项组成的数组。那可以用递归逐步构建完整数组,每层递归追加一项。

    思路如下:

    • 定义函数 fibonacci_array($length, $arr = []),$length 是目标数组长度,$arr 初始为空数组。
    • 计算当前数组长度 $len = count($arr)。
    • 如果 $len 为 0,向 $arr 追加 0;如果 $len 为 1,追加 1;否则追加 $arr[$len-1] + $arr[$len-2]。
    • 如果 count($arr) < $length,就继续递归调用自身,否则返回 $arr。

    调用 fibonacci_array(10) 就能得到一个包含前 10 项的完整数组。

    以上就是四种递归实现斐波那契数列的方法。基础递归适合理解原理,记忆化递归解决了性能问题,尾递归风格让代码更易读,而递归构建数组则直接输出数列。实际开发中,如果 n 不大,直接上基础递归也无妨;但追求效率的话,记忆化是个不错的选择。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 PHP
    相关文章 更多
    PHP 8.6.0 RC7开放测试:预发布包下载、校验与兼容检查方法
    PHP 8.6.0 RC7开放测试:预发布包下载、校验与兼容检查方法

    PHP 8.6.0 RC7已提供源码和Windows预发布构建,用于开发者测试兼容性与回归问题,不适合直接替换生产环境。发布经理预计PHP 8.6.0正式版在11月19日推出;这一日期仍是发布计划。

    Yandex官网入口及网页搜索使用方法
    Yandex官网入口及网页搜索使用方法

    Yandex官网入口是https://www.yondex.net/,该平台支持多语言切换、智能搜索匹配、虚拟键盘变更及实时翻译,提供地图、图片、新闻、购物等垂直服务,并具备账户同步、隐私管理、个性化首页和云存储等功能。

    php怎么连接数据库mysql完整代码与操作步骤
    php怎么连接数据库mysql完整代码与操作步骤

    详细介绍如何使用PHP PDO扩展连接MySQL数据库,包含完整的代码示例、DSN配置方法及异常处理技巧,帮助开发者快速建立稳定安全的数据库连接。

    PHP递归遍历目录文件:RecursiveDirectoryIterator与自定义实现
    PHP递归遍历目录文件:RecursiveDirectoryIterator与自定义实现

    深入解析在PHP中递归遍历多级目录文件的两种核心方案:基于SPL标准库的RecursiveDirectoryIterator高效流式迭代,与基于scandir/opendir的自定义递归函数实现,剖析执行机制、内存表现与实战避坑指南。

    解决PHP递归报错:max_nesting_level限制与内存溢出处理
    解决PHP递归报错:max_nesting_level限制与内存溢出处理

    遇到PHP递归报错时,不要盲目调大max_nesting_level。本文教你区分Xdebug限制、内存耗尽和正则递归错误,提供代码级的终止条件优化与迭代替代方案,彻底解决栈溢出问题。

    PHP递归中static变量与引用传递的常见陷阱及调试
    PHP递归中static变量与引用传递的常见陷阱及调试

    本文分析PHP递归中static变量导致的状态污染及引用传递引发的共享数据修改问题。提供具体的代码复现、缓存键设计建议及调试打印技巧,帮助开发者避免隐蔽的逻辑错误。

    PHP递归性能优化技巧与迭代替代方案
    PHP递归性能优化技巧与迭代替代方案

    解析PHP递归函数在树形数据处理中的性能瓶颈,提供预加载数据消除I/O、使用显式栈替代深层递归的实战方案,帮助开发者在代码可读性与执行效率间做出合理取舍。

    thinkphp项目部署指南详解服务器部署步骤
    thinkphp项目部署指南详解服务器部署步骤

    详细解析ThinkPHP项目在Linux服务器上的部署步骤,包括环境搭建、文件权限、Nginx配置及常见陷阱,提供可复制的代码示例与例外场景分析。

    PHP发送HTTP请求的方法及完整代码教程
    PHP发送HTTP请求的方法及完整代码教程

    详解PHP中发送HTTP请求的常用方法,包括原生cURL配置、file_get_contents流操作及Guzzle库的使用,提供GET/POST请求的完整代码示例与注意事项。

    php解析json内嵌json数据教程及取值方法
    php解析json内嵌json数据教程及取值方法

    本文详解PHP中json_decode处理嵌套JSON数据的机制,对比对象与数组模式的取值差异,提供防止空指针错误的健壮代码示例,帮助开发者快速定位解析失败原因。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。

    即将离开本站
    您即将前往第三方网站,请确认是否继续?