递归与尾递归详解
作者：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, 并放弃所有
局部变量压栈处理，就可以了。这样一来，堆栈根本就没有被占用，每次调用都是重
新使用调用者的堆栈。
尽管尾递归比递归高效，但并非所有的递归算法都可以转成尾递归的，因为尾递归本质
上执行的是迭代的计算过程。这与并非所有的递归算法都可以转成迭代算法的原因是一样的。
参考来源：《计算机程序的构造和解释》
推荐阅读
-
如何精通编程语言：全面指南与实用技巧 ...
[详细]
蜡笔小新 2024-11-07 11:56:01
-
Python与R语言在功能和应用场景上各有优势。尽管R语言在统计分析和数据可视化方面具有更强的专业性，但Python作为一种通用编程语言，适用于更广泛的领域，包括Web开发、自动化脚本和机器学习等。对于初学者而言，Python的学习曲线更为平缓，上手更加容易。此外，Python拥有庞大的社区支持和丰富的第三方库，使其在实际应用中更具灵活性和扩展性。 ...
[详细]
蜡笔小新 2024-11-01 18:37:10
-
-
自从何凯明提出导向滤波后，因为其算法的简单性和有效性，该算法得到了广泛的应用，以至于新版的matlab都将其作为标准自带的函数之一了&#x ...
[详细]
蜡笔小新 2024-11-23 10:46:33
-
本文探讨了Java虚拟机（JVM）中HotSpot实现的垃圾回收（GC）算法，重点介绍了根节点枚举、安全点及安全区域的概念和技术细节，以及这些机制如何影响GC的效率和准确性。 ...
[详细]
蜡笔小新 2024-11-23 09:12:01
-
本文提供了一种有效的方法来解决当Android Studio因电脑意外重启而导致的所有import语句出现错误的问题。通过清除缓存和重建项目结构，可以快速恢复开发环境。 ...
[详细]
蜡笔小新 2024-11-22 11:53:00
-
龙蜥社区的开发者们通过自己的实践和经验，推动着开源技术的发展。本期「龙蜥开发者说」聚焦于一位资深开发者的三次技术转型，分享他在龙蜥社区的成长故事。 ...
[详细]
蜡笔小新 2024-11-21 11:12:28
-
在《POJ 2482 星空中的星星》问题中，通过运用线段树和扫描线算法，可以高效地解决星星在窗口内的计数问题。该方法不仅能够快速处理大规模数据，还能确保时间复杂度的最优性，适用于各种复杂的星空模拟场景。 ...
[详细]
蜡笔小新 2024-11-09 12:09:08
-
本文介绍了计算机视觉领域的最新进展，特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点，为读者提供了全面的概述。 ...
[详细]
蜡笔小新 2024-11-07 12:41:08
-
在本文中，我们将为 HelloWorld 项目添加视图组件，以确保控制器返回的视图路径能够正确映射到指定页面。这一步骤将为后续的测试和开发奠定基础。首先，我们将介绍如何配置视图解析器，以便 SpringMVC 能够识别并渲染相应的视图文件。 ...
[详细]
蜡笔小新 2024-11-07 10:52:57
-
比特币的成功为区块链技术构建了可信货币的基石，标志着区块链1.0时代的到来。以太坊通过引入智能合约，极大地推动了去中心化应用的开发和普及，开启了区块链2.0时代。本文深入探讨了侧链技术在提升区块链扩展性方面的潜力和应用，分析了其在提高交易速度、降低成本和增强安全性等方面的优势，并讨论了当前面临的技术挑战和未来的发展方向。 ...
[详细]
蜡笔小新 2024-10-29 11:24:32
-
本文介绍了使用Python和C语言编写程序来计算一个给定数值的平方根的方法。通过迭代算法，我们能够精确地得到所需的结果。 ...
[详细]
蜡笔小新 2024-11-23 13:50:24
-
本文提供了一个关于AC自动机（Aho-Corasick Algorithm）的详细解析与实现方法，特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念，还重点讲解了如何通过构建失败指针（fail pointer）来提高字符串匹配效率。 ...
[详细]
蜡笔小新 2024-11-23 13:17:52
-
本文提供了一个详尽的前端开发资源列表，涵盖了从基础入门到高级应用的各个方面，包括HTML5、CSS3、JavaScript框架及库、移动开发、API接口、工具与插件等。 ...
[详细]
蜡笔小新 2024-11-23 12:05:53
-
本文介绍了在达梦数据库(DM7)中通过两种方法实现两表之间的联接更新操作，包括使用子查询的更新语句和MERGE语句的具体应用。 ...
[详细]
蜡笔小新 2024-11-23 11:48:24
-
本文深入探讨了TCP协议如何通过滑动窗口和超时重传来确保数据传输的可靠性，同时介绍了流量控制和拥塞控制的基本原理及其在实际网络通信中的应用。 ...
[详细]
蜡笔小新 2024-11-21 18:52:07
-
mobiledu2502906525
这个家伙很懒，什么也没留下！
京公网安备 11010802041100号