August 2021
Beginner to intermediate
450 pages
19h
Chinese
函数可以调用其他函数,这使我们立即想到函数还可以调用自身。Java和大多数现代编程语言一样,在函数调用机制中支持函数调用自身。函数调用自身被称为递归(recursion)。在本节中,我们将研究各种问题的高效的递归解决方案。递归是在本书中经常使用的强大的编程技术。递归的程序通常比非递归程序更紧凑、更易于理解。很少有程序员能在短时间内非常熟练地使用递归,但用递归解决问题会是令人满足的体验,每个程序员都可以有这样的体验(你也可以!)。
递归不仅仅是编程技术。在许多环境中,它是描述真实世界的有效方法。例如,递归树(下图)类似于一棵真实的树,并且具有自然的递归特征。递归模型很好地解释了许多现象。递归在计算机科学中更是起着核心作用,它提供了一个简单的计算模型,能够用于描述任何可以用计算机进行计算的内容;它帮助我们组织和分析程序;它是许多重要的计算应用的关键。递归应用的范围很广,无论是支持信息处理的树数据结构的组合搜索,还是用于信号处理的快速傅里叶变换,都可以使用递归技术来实现。
自然界的递归模型
支持递归技术的一个重要原因是它提供了一种简单直接的方法来构建数学归纳(mathematical induction)的模型。数学归纳法是一种重要的数学证明手段,我们可以用它来证明很多重要的定理。在本书中,我们不再详细介绍数学证明,而只强调编程的方法,但是你们有必要理解这一过程,并明白递归程序在这一过程中的执行过程。
递归图像展示
你的第一个递归程序 如同第一个程序通常是“Hello,World”,第一个递归程序通常是计算阶乘(factorial)函数。正整数n的阶乘函数定义如下: ...