线性递归的形象解释以及尾递归简述

2024-02-22 17:38

本文主要是介绍线性递归的形象解释以及尾递归简述,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

引言:递归函数是一个自我调用的函数。而当递归调用是整个函数体中最后执行的语句并且它的返回值不用于任何表达式的一部分时,这个递归调用就是尾递归。——定义虽然准确而精炼,但往往看起来不像人话


限于笔者水平,本文对递归的解释并不深入,欢迎指正。


一、线性递归: “把大象装冰箱”(附代码):

  • 嫌麻烦可以直接看代码 ^.^ 。

    1. 假设你持有一枚大象,你想把它装进冰箱,这时候,你以为只需要做三件事:开门,放大象,关门。然而事情没这么简单。
    2. 冰箱里有一张纸条,写着一个数字9527。
    3. 我们假设开门的全套动作要包括:大喊“芝麻开门”,鼓掌,开门。
    4. 关门的全套动作包括:大喊纸条的数字,关门,并把纸条的数字减1。
    5. 你的目的除了搞定大象之外,还有——计算纸条的最终数字。
    6. 于是你试着第1次执行开门动作:“芝麻开门!”,啪啪啪,开门…
    7. 发现没有纸条,但是里面还有一个冰箱,于是你只好继续执行第2次开门的动作…
    8. 发现没有纸条,但是里面还有一个冰箱,于是你只好继续执行第3次开门的动作…
    9. 终于在你执行完第250次开门的动作之后,一个纸条(返回值)闪亮登场。于是你不再执行下一次开门,而是把大象放了进去。
    10. 纸条上写着“9527”。
    11. 你大喊“9527”,关上第一道门,并把纸条改成“9526”…
    12. 你大喊“9526”,关上第二道门,并把纸条改成“9525”…
    13. 最后你把所有门关上,程序结束,纸条上的数字变成了“9277”。
    14. PS:这里“放置大象”代表你想要在获取返回值的同时执行的动作[1],而纸条的数字代表你在最深层获取的返回值[2],“发现纸条”这个事件则是“递归终止条件”[3]。
  • 代码:为简短,终止条件改为n==2


public class E00_Recursive {private static int a;  // 如果变量定义在方法内部,那么每层递归都将建立一个新变量,造成更多开销。static int f(int n) {System.out.print("芝麻开门,");System.out.println("啪啪啪," + "开门");// 开始寻找返回值(找纸条)if (n == 2) {  // 发现纸条,递归终止 [3]System.out.println("------放大象------");  // [1]a = 9527;  // 返回值 [2]} elsea = f(n + 1) - 1;System.out.print("喊" + a);System.out.println(",关门");return a;}public static void main(String[] args) {System.out.println(f(0));}
}
/* 结果
芝麻开门, 啪啪啪, 开门
芝麻开门, 啪啪啪, 开门
芝麻开门, 啪啪啪, 开门
------放大象------
喊9527, 关门
喊9526, 关门
喊9525, 关门
9525
*/
其实在IDE里设置debug断点,进行单步调试,跑一个斐波那契之类的demo,也有助于理解。

扩展思考:试想如果在方法体内部有两个递归调用语句(比如斐波那契的线性递归),那么按理说会造成1个调2个,2个调4个这种指数级的开销。但是对此我有些不解,实际上,如果我们把两个调用看做程序的两条线路,那么在任何一次调用中,两条路线都不会同时执行,只有在一条路线结束并返回后,另一条才会执行,所以实际的开销仍然是线性变化的。留作以后研究。


二、进阶:尾递归(附代码)

嫌废话请直接看代码,嘿嘿

上面的例子,每一层递归调用时,都要保存上层函数的状态,去等待下一层的返回值。这势必对栈内存造成额外的开销。那么该如何解决呢?
(底层调用过程我也不懂,只是大概知其然)

那么既然如此,显然我们现在的目标就是:不让函数保存调用的状态,即是说:函数在向下一层递归前进后,上一层应该只等待返回值,而没有等待执行的其他操作。这种特点让编译器可以对栈的使用进行优化。

  • 那么想让函数具备这种特点,还要进行以下思考:
    • 首先,既然保证上层函数“只”等待返回值,那么f(n-1)-1就不合要求,因为它有等待执行的操作“减1”。这样,值就不能在方法体内部迭代了,咋办呢?
    • 聪明的前辈们想到了增加参数的办法,去代替迭代的表达式,见代码。
    • 但是即便解决了迭代值的问题,我们的关门动作又该如何执行呢?现在函数状态不保存,我们怎么一层一层地回溯来关门呢。
    • 答案是:解决不了,只能不关门。(如果有误希望大佬给个提示)
    • 那么废话不多说,直接上代码,为了简便,我们在n==3时终止递归:

public class E00_TailRecursive {static int recursive(int n, int a){System.out.println("开门动作");if (n == 3){System.out.println("放大象");return a; // n==3时,传入的a值已经是经过多次减1计算得到的9524了。} else// 参数里的a-1 一开始可能不太好理解。实际上相当于我们一开始就拿到纸条,每递归一次就减1。而n仅仅用来控制递归层级。return recursive(n + 1, a - 1);  // 递归调用是最后一行代码,且不属于表达式的一部分}public static void main(String[] args) {System.out.println(recursive(0, 9527));}
}
/* Output
开门动作
开门动作
开门动作
开门动作
放大象
9524*/

最后再看尾递归定义应该就更好理解了:当递归调用是整个函数体中最后执行的语句并且它的返回值不用于任何表达式的一部分时,这个递归调用就是尾递归。

线性递归和尾递归在开销方面的直观展示:

线性递归:保存每一步等待返回值

f(0)

{ f(1) - 1}

{ { f(2) -1 } - 1}

{ { { f(3) - 1 } -1 } - 1}

{ { { 9527 - 1 } -1 } - 1}

{ { 9526 -1 } - 1}

{ 9525 - 1}

9524

尾递归: 直接等价替换成另外一个调用,最终返回值其实是最后一个函数的返回值

recursive(0, 9527)

recursive(1, 9526)

recursive(2, 9525)

recursive(3, 9524) -> 9524

  • 这是我目前对递归的理解,感谢阅读,欢迎指正。

这篇关于线性递归的形象解释以及尾递归简述的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/736004

相关文章

mysql递归查询语法WITH RECURSIVE的使用

《mysql递归查询语法WITHRECURSIVE的使用》本文主要介绍了mysql递归查询语法WITHRECURSIVE的使用,WITHRECURSIVE用于执行递归查询,特别适合处理层级结构或递归... 目录基本语法结构:关键部分解析:递归查询的工作流程:示例:员工与经理的层级关系解释:示例:树形结构的数

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

wolfSSL参数设置或配置项解释

1. wolfCrypt Only 解释:wolfCrypt是一个开源的、轻量级的、可移植的加密库,支持多种加密算法和协议。选择“wolfCrypt Only”意味着系统或应用将仅使用wolfCrypt库进行加密操作,而不依赖其他加密库。 2. DTLS Support 解释:DTLS(Datagram Transport Layer Security)是一种基于UDP的安全协议,提供类似于

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

✨机器学习笔记(二)—— 线性回归、代价函数、梯度下降

1️⃣线性回归(linear regression) f w , b ( x ) = w x + b f_{w,b}(x) = wx + b fw,b​(x)=wx+b 🎈A linear regression model predicting house prices: 如图是机器学习通过监督学习运用线性回归模型来预测房价的例子,当房屋大小为1250 f e e t 2 feet^

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

【高等代数笔记】线性空间(一到四)

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速