递归与尾递归详解
作者：mobiledu2502906525 | 来源：互联网 | 2023-01-26 11:29
递归与尾递归详解下面两个程序是scheme(Lisp语言)写的计算阶乘的递归和尾递归实现线性递归：(define(factorialn)(if(n1)1(*n(factorial(-
递归与尾递归详解
下面两个程序是scheme(Lisp语言)写的计算阶乘的递归和尾递归实现
线性递归：
(define (factorial n)
(if (=n 1)
1
(* n (factorial (- n 1)))))
尾递归：
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
用C写出来就是这样的：
线性递归：
long factorial(long n)
{
return(n == 1) ? 1 : n * factorial(n - 1);
}
尾递归：
long fact_iter(long product, long counter, long maxcount)
{
return (counter > maxcount) ? product : fact_iter(product*counter, counter+1, maxcount);
}
long factorial(long n)
{
return fact_iter(1, 1, n);
}
线性递归程序基于阶乘的递归定义，即：对于一个正整数n，n!就等于n乘以(n-1)!:
n! = n[(n-1)(n-2)…3*2*1] =n(n-1)!
程序一在计算4!时的过程是这样的：
(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
而尾递归程序用的是另一种计算规则，即先用1乘以2，再将得到的结果乘以3，再乘以4，这样下
去直到n。程序中维持着一个变动中的乘积product，以及一个从1到n的计数器counter,这一
计算过程中的product和counter在每一步都按照下面规则改变：
product = counter * product
counter = counter + 1
这样循环下去，可以得到n!也就是计数器counter超过n时乘积product的值。
所以程序二在计算4!的过程是这样的：
(factorial 4)
(fact-iter 1 1 4)
(fact-iter 1 2 4)
(fact-iter 2 3 4)
(fact-iter 6 4 4)
(fact-iter 24 5 4)
24
一个对自己本身的递归尾调用，就叫做尾递归。这里尾调用的“尾”字，是指运行
时需要执行的最后一个动作。不是简单的语法字面上的最后一个语句。 尾递归实
际执行的是迭代的计算过程。
线性递归函数必须满足以下两个基本属性：
*必须清晰无误地解决基的情况。
*每一个递归的调用，必须包含更小的参数值。
而尾递归则不必满足这两个条件。
普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程调用都使得调
用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就不存在这样的问
题, 因为它的状态完全由函数的参数保存. 并且，由于尾递归的函数调用出现在调用者
函数的尾部，因为是尾部，所以根本没有必要去保存任何局部变量，sp, pc的信息。
直接让被调用的函数返回时越过调用者，返回到调用者的调用者去。
尾调用优化不是什么很复杂的优化，实际上几乎所有的现代的高级语言编译器都支持
尾调用这个很基本的优化。 实现层面上，只需要把汇编代码call改成jmp, 并放弃所有
局部变量压栈处理，就可以了。这样一来，堆栈根本就没有被占用，每次调用都是重
新使用调用者的堆栈。
尽管尾递归比递归高效，但并非所有的递归算法都可以转成尾递归的，因为尾递归本质
上执行的是迭代的计算过程。这与并非所有的递归算法都可以转成迭代算法的原因是一样的。
参考来源：《计算机程序的构造和解释》
推荐阅读
-
本文介绍了Android中高级面试的必知必会内容，并总结了相关经验。文章指出，如今的Android市场对开发人员的要求更高，需要更专业的人才。同时，文章还给出了针对Android岗位的职责和要求，并提供了简历突出的建议。 ...
[详细]
蜡笔小新 2023-12-14 14:53:02
-
本文介绍了学习SLAM的女生的故事，她们选择SLAM作为研究方向，面临各种学习挑战，但坚持不懈，最终获得成功。文章鼓励未来想走科研道路的女生勇敢追求自己的梦想，同时提到了一位正在英国攻读硕士学位的女生与SLAM结缘的经历。 ...
[详细]
蜡笔小新 2023-12-14 17:55:18
-
-
生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型，可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ...
[详细]
蜡笔小新 2023-12-14 17:51:18
-
在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ...
[详细]
蜡笔小新 2023-12-14 17:34:00
-
本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ...
[详细]
蜡笔小新 2023-12-14 16:49:01
-
近年来，大数据成为互联网世界的新宠儿，被列入阿里巴巴、谷歌等公司的战略规划中，也在政府报告中频繁提及。据《大数据人才报告》显示，目前全国大数据人才仅46万，未来3-5年将出现高达150万的人才缺口。根据领英报告，数据剖析人才供应指数最低，且跳槽速度最快。中国商业结合会数据剖析专业委员会统计显示，未来中国基础性数据剖析人才缺口将高达1400万。目前BAT企业中，60%以上的招聘职位都是针对大数据人才的。 ...
[详细]
蜡笔小新 2023-12-14 16:25:20
-
本文介绍了Java工具类库Hutool，该工具包封装了对文件、流、加密解密、转码、正则、线程、XML等JDK方法的封装，并提供了各种Util工具类。同时，还介绍了Hutool的组件，包括动态代理、布隆过滤、缓存、定时任务等功能。该工具包可以简化Java代码，提高开发效率。 ...
[详细]
蜡笔小新 2023-12-14 14:29:36
-
本文介绍了高校天文共享平台的开发过程中的思考和规划。该平台旨在为高校学生提供天象预报、科普知识、观测活动、图片分享等功能。文章分析了项目的技术栈选择、网站前端布局、业务流程、数据库结构等方面，并总结了项目存在的问题，如前后端未分离、代码混乱等。作者表示希望通过记录和规划，能够理清思路，进一步完善该平台。 ...
[详细]
蜡笔小新 2023-12-13 18:08:58
-
本文介绍了神经网络优化中常用的优化方法，包括学习率调整和梯度估计修正，并通过实验验证了不同优化算法的效果。实验结果表明，Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ...
[详细]
蜡笔小新 2023-12-13 16:05:14
-
本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ...
[详细]
蜡笔小新 2023-12-13 15:38:19
-
本文介绍了在Windows环境下如何配置php+apache环境，包括下载php7和apache2.4、安装vc2015运行时环境、启动php7和apache2.4等步骤。希望对需要搭建php7环境的读者有一定的参考价值。摘要长度为169字。 ...
[详细]
蜡笔小新 2023-12-13 10:39:24
-
本文介绍了Android源码中的JNI技术，包括概述和应用。JNI是Java Native Interface的缩写，是一种技术，可以实现Java程序调用Native语言写的函数，以及Native程序调用Java层的函数。在Android平台上，JNI充当了连接Java世界和Native世界的桥梁。本文通过分析Android源码中的相关文件和位置，深入探讨了JNI技术在Android开发中的重要性和应用场景。 ...
[详细]
蜡笔小新 2023-12-13 10:00:57
-
本文介绍了在多平台下进行条件编译的必要性，以及具体的实现方法。通过示例代码展示了如何使用条件编译来实现不同平台的功能。最后总结了只要接口相同，不同平台下的编译运行结果也会相同。 ...
[详细]
蜡笔小新 2023-12-13 09:38:06
-
本文总结了AAC解码的过程，并介绍了几个解码版本，包括FAAD/2、FFmpeg自带的解码器以及opencore的opencore-aacdec。作者选择了FAAD作为解码器，并通过编译和运行测试确认解码无问题。然而，作者在输出过程中遇到了时长增加一倍的问题，通过修改代码实现了单通道输出，并解决了时长异常的问题。最终，解码后的声音质量接近无损。 ...
[详细]
蜡笔小新 2023-12-13 09:01:04
-
人类并不是唯一能够在镜子中认出自己的生物，但拥有自我意识的物种并不多，只有寥寥可数的几种。自我意识是如何产生的？其作用又是什么 ...
[详细]
蜡笔小新 2023-12-13 08:24:08
-
mobiledu2502906525
这个家伙很懒，什么也没留下！
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 