当前位置: 开发笔记 > 前端 > 正文

递归与尾递归详解

作者：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, 并放弃所有

局部变量压栈处理，就可以了。这样一来，堆栈根本就没有被占用，每次调用都是重

新使用调用者的堆栈。

尽管尾递归比递归高效，但并非所有的递归算法都可以转成尾递归的，因为尾递归本质

上执行的是迭代的计算过程。这与并非所有的递归算法都可以转成迭代算法的原因是一样的。
参考来源：《计算机程序的构造和解释》

推荐阅读

dom
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
dom
Go语言基础：Hello World 实践

本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ... [详细]

蜡笔小新 2024-12-27 21:29:35
dom
Linux 网卡绑定的七种工作模式详解

本文深入探讨了Linux系统中网卡绑定（bonding）的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡，实现网络冗余、带宽聚合和负载均衡，在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]

蜡笔小新 2024-12-27 10:18:13
dom
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
dom
libsodium 1.0.15 发布：引入重大不兼容更新

最新发布的 libsodium 1.0.15 版本带来了若干不兼容的变更，其中包括默认密码散列算法的更改和其他重要调整。 ... [详细]

蜡笔小新 2024-12-26 11:03:58
scheme
MySQL事务管理：启动、设置、锁与解锁详解

本文详细介绍了MySQL 5.5及以上版本中事务管理的全过程，包括事务的启动、设置、锁机制以及解锁方法，旨在为开发者提供一个清晰、全面的操作指南，避免因网络资料分散而导致的学习障碍。 ... [详细]

蜡笔小新 2024-11-30 17:49:46
scheme
深入解析Android自定义View面试题

本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ... [详细]

蜡笔小新 2024-12-28 11:15:04
scheme
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
scheme
Understanding Life: A Forward-Living, Backward-Reflecting Paradox

Søren Kierkegaard famously stated that life can only be understood in retrospect but must be lived moving forward. This perspective delves into the intricate relationship between our lived experiences and our reflections on them. ... [详细]

蜡笔小新 2024-12-28 10:17:59
scheme
计算机网络复习：第五章网络层控制平面

本文探讨了网络层的控制平面，包括转发和路由选择的基本原理。转发在数据平面上实现，通过配置路由器中的转发表完成；而路由选择则在控制平面上进行，涉及路由器中路由表的配置与更新。此外，文章还介绍了ICMP协议、两种控制平面的实现方法、路由选择算法及其分类等内容。 ... [详细]

蜡笔小新 2024-12-27 22:54:11
scheme
HDFS与Hive中的数据存储和管理机制

本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射，详细解释了两者的创建、加载及删除操作，并提供了查看表详细信息的方法。通过对比这两种表类型，帮助读者理解如何更好地管理和保护数据。 ... [详细]

蜡笔小新 2024-12-27 20:21:48
scheme
理解感受野与锚框在目标检测中的应用

本文探讨了卷积神经网络（CNN）中感受野的概念及其与锚框（anchor box）的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小，而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]

蜡笔小新 2024-12-27 12:03:44
scheme
2023年京东Android面试真题解析与经验分享

本文由一位拥有6年Android开发经验的工程师撰写，详细解析了京东面试中常见的技术问题。涵盖引用传递、Handler机制、ListView优化、多线程控制及ANR处理等核心知识点。 ... [详细]

蜡笔小新 2024-12-26 17:45:48
scheme
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新 2024-12-26 08:55:03
js
并发编程：深入理解设计原理与优化

本文探讨了并发编程中的关键设计原则，特别是Java内存模型（JMM）的happens-before规则及其对多线程编程的影响。文章详细介绍了DCL双重检查锁定模式的问题及解决方案，并总结了不同处理器和内存模型之间的关系，旨在为程序员提供更深入的理解和最佳实践。 ... [详细]

蜡笔小新 2024-12-26 01:14:06

mobiledu2502906525

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章