递归与尾递归详解
作者：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, 并放弃所有 局部变量压栈处理，就可以了。这样一来，堆栈根本就没有被占用，每次调用都是重 新使用调用者的堆栈。 尽管尾递归比递归高效，但并非所有的递归算法都可以转成尾递归的，因为尾递归本质 上执行的是迭代的计算过程。这与并非所有的递归算法都可以转成迭代算法的原因是一样的。 参考来源：《计算机程序的构造和解释》
推荐阅读
本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ...
[详细]
蜡笔小新 2024-12-27 13:55:14
本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ...
[详细]
蜡笔小新 2024-12-27 21:29:35
本文深入探讨了Linux系统中网卡绑定（bonding）的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡，实现网络冗余、带宽聚合和负载均衡，在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ...
[详细]
蜡笔小新 2024-12-27 10:18:13
本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ...
[详细]
蜡笔小新 2024-12-26 15:38:03
最新发布的 libsodium 1.0.15 版本带来了若干不兼容的变更，其中包括默认密码散列算法的更改和其他重要调整。 ...
[详细]
蜡笔小新 2024-12-26 11:03:58
本文介绍如何仅使用Numpy库，通过双线性插值方法实现图像的高效缩放，避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理，并提供了完整的代码示例。 ...
[详细]
蜡笔小新 2024-12-28 13:15:40
本文深入探讨了图形显卡的进化历程，重点介绍了非公版RTX 3080显卡的技术特点和创新设计。 ...
[详细]
蜡笔小新 2024-12-28 13:07:40
本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准，旨在为第三方应用提供安全的用户资源访问授权，同时确保用户的账户信息（如用户名和密码）不会暴露给第三方。 ...
[详细]
蜡笔小新 2024-12-28 12:07:46
本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ...
[详细]
蜡笔小新 2024-12-28 11:15:04
Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ...
[详细]
蜡笔小新 2024-12-28 09:44:49
在工作期间想要浏览微信和朋友圈却不太方便？虽然微信电脑版目前不支持直接刷朋友圈，但通过远程投屏技术，可以轻松实现在电脑上操作安卓设备的功能。 ...
[详细]
蜡笔小新 2024-12-26 15:23:19
本文深入探讨了 Java 编程语言的基础，特别是其跨平台特性和 JVM 的工作原理。通过介绍 Java 的发展历史和生态系统，帮助初学者理解如何编写并运行第一个 Java 程序。 ...
[详细]
蜡笔小新 2024-12-26 15:03:43
本文深入探讨了C++中构造函数的初始化列表，包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明，详细解释了初始化列表在对象创建时的重要性。 ...
[详细]
蜡笔小新 2024-12-26 14:19:13
2013年5月9日，PHP官方发布了PHP 5.5.0rc1和PHP 5.4.15正式版，这两个版本均支持64位环境。本文将详细介绍Zend OPcache的功能及其在Windows环境下的配置与测试。 ...
[详细]
蜡笔小新 2024-12-26 12:56:20
本文详细介绍了Java泛型的概念及其在JDK 5中的应用，通过具体代码示例解释了泛型的引入、作用和优势。同时，探讨了泛型类、泛型方法和泛型接口的实现，并深入讲解了通配符的使用。 ...
[详细]
蜡笔小新 2024-12-26 11:15:56
mobiledu2502906525
这个家伙很懒，什么也没留下！
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
