HDU-CS-WIKI

Appearance

Recursive Functions 递归函数 ​

什么是递归函数？简单讲，就是如果函数体调用了函数本身，要么直接调用，要么间接调用，那这个函数就是递归函数。换句话讲，执行递归函数的过程中，函数可能需要应用自身。我们借用一下维基百科上的定义[1]：

递归（英语：recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此有很多在函数编程语言（如 Scheme）中用递归来取代循环的例子。

在 Python 中写递归其实并不复杂，我们可以先参考这一节[2]的内容，对递归有一个大致的了解，熟悉一下是什么。 递归的两个特征就是结束条件于自我调用，我们这里先用比较抽象的方式去定义一个自我递归的函数。

python
def recursive_function(n):
    if (<end condition>) :
        return <return value>
    return recursive_function(<new argument>)

这里的 <new argument> 通常是更小规模的问题。

我们将从一个例题开始：编写一个函数，求一个自然数的位数之和。在设计递归函数时，我们会寻找可以将问题分解成更简单问题的方法。在本例中，运算符 % 和 // 可用来将一个数字分成两部分：最后一位数字和除最后一位数字之外的所有数字。

python
>>> 114514 % 10
4
>>> 114514 //10
11451

114514 的各位数字之和是 1+1+4+5+1+4 = 15。正如我们可以把数字分开一样，我们也可以把这个和分成最后一个数字 4 和 除最后一个数字外的所有数字之和 1+1+4+5+1 = 11。这种分离给我们提供了一种算法：要求一个数字 n 的位数之和，将其最后一位数 n % 10 与 n // 10 的位数之和相加。有一种特殊情况：如果一个数只有一位数，那么它的数位之和就是它本身。这种算法可以用递归函数来实现。

python
def sum_digits(n):
    """Return the sum of the digits of positive integer n."""
    if n < 10:
        return n
    else:
        all_but_last, last = n // 10, n % 10
        return sum_digits(all_but_last) + last

该 sum_digits 的定义是完整且正确的，尽管 sum_digits 函数在函数体内调用自己。将数字的各个数字相加的问题分解为两个步骤：计算除最后一位数字外所有数字的总和，然后将最后一位数字相加。这两个步骤都比原问题简单。该函数是递归的，因为第一步与原始问题是同一类型的问题。也就是说， sum_digits 正是我们在实现 sum_digits 时所需的函数。 还有几种常见的递归过程比如相互递归和树递归咱就不多赘述了～～（因为想开始夹带私货了）~~，只要理解了上面这个例子，其他的几种过程都很容易理解。

很有趣的是，在自然语言中，我们会无意识的去应用递归这种结构。考虑这个句子

  • "The cat that the dog chased ran away." 在这个句子中，"The cat ran away"是一个完整的句子。但是我们在主语"cat"后面嵌入了另一个句子"that the dog chased"来修饰"cat"。这个嵌套结构可以继续延伸：
  • "The cat that the dog that the boy scared chased ran away." 在这个句子中，"The dog that the boy scared"嵌套在"The cat that the dog chased" 里面，从而形成了递归结构。 再考虑一段套娃的对话：
  • 他们在撒谎
  • 我们知道（他们在撒谎）
  • 他们知道 [我们知道 (他们在撒谎)]
  • 我们也知道 {他们知道 [我们知道 (他们在撒谎)]} 人类语言的独特性在于可以用有限的规则与参数创造出无限的句子，这个特点便意味着人类的语言有递归行，语言系统具有生成性，这就引出了另一个话题 —— 生成语法。如果对生成语法感兴趣可以去知乎上看看这篇文章[3] 。

Language is:

  • A finite set of fundamental principles that are common to all languages。
  • A finite set of parameters that determine syntactic variability among languages ——Norm Chomsky 而提到生成语法就不得不提一嘴乔姆斯基老爷子了，乔姆斯基对语言层级的划分主要体现在他提出的乔姆斯基层级（Chomsky Hierarchy），这是一种用于分类各种文法和语言的理论框架。乔姆斯基层级主要分为四个级别，从低到高分别是：有限状态文法、上下文无关文法、上下文相关文法和递归可枚举文法。这些层级在形式语言理论中尤其重要，广泛应用于计算机科学和语言学中。我们这里快速的介绍下这个框架，如果有兴趣的话可以这本书[4]。
  1. 递归可枚举文法（零型文法）：这是最复杂的文法类型，理论上可以生成任何可能的语言，包括所有计算机程序的输出。这种文法的解析和执行通常非常复杂，甚至可能是不可判定的。
  2. 上下文相关文法（一型文法）：这类文法更加复杂，可以生成的语言包括某些自然语言和复杂的数据结构。在计算机科学中，这类文法用于解决某些特定的算法问题，但由于其解析过程通常较为复杂，实际应用较少。
  3. 上下文无关文法（二型文法）：这类文法可以生成更复杂的语言结构，如程序设计语言中的表达式和语句。编程语言的语法大多是上下文无关的，因为它允许设计复杂的嵌套结构，例如括号匹配和树形结构，常见于编译器的设计。
  4. 有限状态文法（三型文法）：这种文法由有限的状态和转换规则构成，适用于描述简单的结构，如正则表达式和有限自动机。在计算机科学中，它通常用于设计文本搜索模式和分析简单的输入数据。

一般我们认为编程语言大多数位于上下文无关文法这一层级，因为这能够很好地描述编程语言中常见的结构，如函数、循环和条件语句，且相对容易通过编译器进行解析和处理。上下文无关语法由四个部分组成：

  • 非终结符（Non-terminal symbols）：这些是语法的变量，代表了可以被进一步替换和扩展的语言的组成部分。
  • 终结符（Terminal symbols）：这些是语言的基本单位，不可进一步分解。在编程语言中，例如，终结符可能包括关键字、操作符、数值等。
  • 产生式规则（Production rules）：这些规则定义了非终结符如何被终结符或非终结符的序列替换和重新组合。
  • 起始符号（Start symbol）：定义了产生式规则开始应用的非终结符。

以简单的数学表达式语法为例，其 CFG (Context Free Language) 可能如下：

  • 非终结符：Expr, Term, Factor = 终结符：+, *, (,), Number
  • 产生式规则：
    • Expr → Expr + Term | Term
    • Term → Term * Factor | Factor
    • Factor → ( Expr ) | Number
  • 起始符号：Expr 此例中，Expr、Term 和 Factor 非终结符通过递归产生式规则相互定义，支持加法和乘法运算，以及括号内的表达式求值。这里我们暂时假设 Number 指 0~9 之间的数字。 具体而言，比如说我们想生成一个数学表达式 1 + 1 +4 * 5 *1 + 4
bash
# 起始符号
Expr
# 应用产生式规则 Expr → Expr + Term
Expr + Term
# 继续应用产生式规则 Expr → Expr + Term
Expr + Term + Term
# 继续应用产生式规则 Expr → Term
Term + Term + Term
# 应用产生式规则 Term → Factor
Factor + Term + Term
# 应用产生式规则 Factor → Number
Number + Term + Term
# 将Number替换为1
1 + Term + Term
# 继续应用产生式规则 Term → Factor
1 + Factor + Term
# 应用产生式规则 Factor → Number
1 + Number + Term
# 将Number替换为1
1 + 1 + Term
# 继续应用产生式规则 Term → Term * Factor
1 + 1 + Term * Factor
# 应用产生式规则 Term → Term * Factor
1 + 1 + Term * Factor * Factor
# 继续应用产生式规则 Term → Factor
1 + 1 + Factor * Factor * Factor
# 应用产生式规则 Factor → Number
1 + 1 + Number * Factor * Factor
# 将Number替换为4
1 + 1 + 4 * Factor * Factor
# 应用产生式规则 Factor → Number
1 + 1 + 4 * Number * Factor
# 将Number替换为5
1 + 1 + 4 * 5 * Factor
# 应用产生式规则 Factor → Number
1 + 1 + 4 * 5 * Number
# 将Number替换为1
1 + 1 + 4 * 5 * 1
# 继续应用产生式规则 Expr → Expr + Term
Expr + Term
# 应用产生式规则 Expr → Term
Term + Term
# 应用产生式规则 Term → Factor
Factor + Term
# 应用产生式规则 Factor → Number
Number + Term
# 将Number替换为4
4 + Term
# 应用产生式规则 Term → Factor
Factor
# 应用产生式规则 Factor → Number
Number
# 将Number替换为4
4
# 最终生成的表达式
1 + 1 + 4 * 5 * 1 + 4

上下文无关语法的这种能力使其成为理解和构建复杂语言结构的强大工具，尽管它也有其局限性，例如在处理某些自然语言现象时的困难。 而再编程语言领域，我们有巴克斯 - 诺尔范式（BNF）用于定义上下文无关文法。它由约翰・巴克斯（John Backus）和彼得・诺尔（Peter Naur）在 20 世纪 50 年代和 60 年代引入，用来定义编程语言的语法规则。BNF 使用一组产生式规则（也称为文法规则）来描述语言的句法结构。 BNF 的语法规则通常写成如下形式

txt
<非终结符> ::= <表达式>

其中，<非终结符> 是一个非终结符，< 表达式 > 是由终结符和非终结符组成的序列，表示如何生成该非终结符的句法结构。::= 是定义符号，表示 “可以被替换为”。 而对于上面这个例子，我们用 BNF 来更严格的定义一下：

txt
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= <number> | ( <expr> )
<number> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

在实践中，为了提高 BNF 的表达能力，人们引入了扩展的 BNF（Extended Backus-Naur Form，EBNF）。EBNF 增加了一些新的符号，使得文法描述更加简洁和直观。这里就不多讲赘述了，可以去看看编译原理之类的（）。 私货好像有点多了，打住。

聊了这么多，让我们回到递归这个概念，我们首先来探讨一下汉诺塔这个经典的智力游戏。它是由法国数学家爱德华・卢卡斯于 1883 年发明的．给定一个由 8 个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上。我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面，最少要移动多少次才能完成这个任务。

乍一眼看下去这个问题似乎有些棘手，而解决这类问题最好的办法是先将这个问题推广，换言之，便是把这个八个圆盘的问题转换为 n 个圆盘的问题。

这样推广的好处在于我们可以先从小问题入手，再根据数学归纳法推广到更一般的情况。我们先引入一些记号来方便命名与求解。我们说Tn 是这个问题的最优解，也就说对于一个 n 层的汉诺塔，我们至少要通过Tn 次移动，才能把整个塔移动到另一根桩柱上，而且较大的圆盘在移动过程中不能放置在较小的圆盘上面。

我们很容易可以观察到当层数比较低时，T1=1,T2=3。而从这两个情况我们还能知道T0=0，也就是 0 个圆盘的汉诺塔不需要任何移动。

那么当 n 比较大的时候，我们要怎么操作呢，我们在前两个例子中看到，我们的做法是先将n−1 个小的圆盘移到一个不同的柱上，然后移动底下最大的圆盘，然后再把那 n-1 个小圆盘移动到那个最大的圆盘上面去。

我们用数学的语言重新描述一下，就是我们需要进行Tn−1 次移动，将n−1 个圆盘移开，然后再进行Tn−1 次移动把移开的圆环移到最大的圆环底下，所以Tn≤2Tn−1+1。

但是现在我们只给出了一个上限，那么是否存在更好地方法使得Tn 更小呢？实际上没有，考虑到我们要将n−1 个小的圆盘移到一个不同的柱上，这就需要要Tn−1 次移动，而将n−1 个圆盘移到最大的圆盘底下，同样需要Tn−1 次移动，如果我们在这两个移动的过程中间犯了一些小错误，那我们会移动次数增加。所以我们可以得到Tn≥2Tn−1+1。

结合两个两个等式与n=0 的平凡解，我们可以得到

T0=0Tn=2n+1，n≥0

而上面这一组式子我们称为递归式。它给出一个边界值，以及一个推导一般情况的方程。有时我们也把单一的那个方程成为递归式，不过理论上他还需要一个边界值。

我们用 python 代码表示这个递归式：

python
def Hanoi(n):
    if (n == 0):
        return 0
    elif (n > 0):
        return 2*Hanoi(n-1) + 1

一般来说当 n 变得很大时，我们并不会用递归式去求值，因为太耗时了。其中的原因在于递归式只给出了一个局部的信息，而计算Tn 是需要从头开始获取前面的局部信息，所以说我们需要一个递归式的 "封闭" 解 (通项公式)，这个解可以直接计算出Tn, 甚至当 n 很大的时候也一样可以。

那么如何求解呢，一个办法是用惊人的注意力不难发现Tn 的递归解是Tn=2n−1。但是这不严谨，而且当这个递归式变得复杂的时候，我们很难直接观察到这样一个递归解。

这时候我们就需要数学归纳法登场了。数学归纳法（mathematical induction）是证明某个命题对所有满足 n≥n0 的整数 n 都成立的一般方法．首先我们在 n 取最小值 n0 时证明该命题，这一步骤称为基础（basis）；然后对 n>n0 ，假设该命题对 n0 与 n>n0 之间（包含它们在内）的所有值都已经被证明，再证明该命题对 n 成立，这一步骤称为归纳（induction）。这样一种证明方法仅用有限步就得到无限多个结果。

而对于这个例子来说数学归纳法确实可以证明得到这个递归解

河内塔的递归式是在各种应用中出现的诸多问题的一个典范．在寻求像Tn 这样有意义的量的封闭形式的表达式时，我们经过了如下三个阶段。

(1) 研究小的情形．这有助于我们洞察该问题，而且对第二和第三阶段有所帮助． (2) 对有意义的量求出数学表达式并给出证明．对河内塔，这就是递归式，它允许我们对任何n 算Tn （假设我们有这样的意向）. (3) 对数学表达式求出封闭形式并予以证明．对河内塔，这就是求递归解。

我们在这里先不谈怎么求出这个递归解，如果有兴趣的话可以去看看这本《具体数学》[5]，上面这个例子就是从这本书中选的。

再次回到正题，那么我们要怎么写递归函数呢？

有了上面的铺垫，我们可以可以归纳一下步骤：

  1. 找出递归式，也就是递归函数的主体部分。
  2. 找到一个特殊值（通常是一个边界值）
  3. 每次调用函数时根据递推式缩小问题的规模。

考虑一个经典的走楼梯的问题：想象一下，你想要走上一个有 n 级台阶的楼梯，其中 n 是一个正整数。每次移动可以一次迈一步或两步。有多少种方法可以走完整个楼梯？

对于这个问题，我们可以使用递归函数来解决。

不难发现 n 级台阶的走法可以由 n-1 级台阶和 n-2 级台阶组成，所以问题可以分解为两个子问题，即走 n-1 级台阶和走 n-2 级台阶。而初始情况是什么呢？初始情况就是走 1 级台阶和走 2 级台阶。于是我们可以得到下面这个函数

python
def count_ways_recursive(n):
    if n == 0 or n == 1:
        return 1  # One way to stay on the ground or take one step to the first stair.
    if n < 0:
        return 0  # No way to climb negative steps.
    return count_ways_recursive(n - 1) + count_ways_recursive(n - 2)

对于默认的 return 语句中的 return count_ways_recursive(n - 1) + count_ways_recursive(n - 2) ，最开始写这种递归的时候可能会困惑这样写真的能求出来正确的答案吗？实际上，我们可以把它理解为对这是子问题的一个抽象，我们不需要知道它在做什么，只需要知道它在求解一个子问题就可以了。这一步我们称之为递归的信仰之跃 (Recursive Leap of Faith)。 还有一个经典但是优雅的例子便是归并排序 (merge sort)，感兴趣的同学可以去 OI Wiki 上看看。[6]

  1. 递归 ↩︎

  2. Recursive Functions ↩︎

  3. 【生成语法】框架设计：从短语结构规则，到 X-bar 理论，再到合并 ↩︎

  4. Introduction to Automata Theory, Languages, and Computation ↩︎

  5. Concrete Mathematics ↩︎

  6. 递归 & 分治 ↩︎

Made with ❤️ by ALL 协作者

Copyright © 2023-present Evan You && ALL 协作者