3. 递归

2024-03-09 00:12:59 阅读 0

如果一个概念的定义需要使用概念本身，我们说它的定义是递归的（）。例如：

习惯了。

这只是一个笑话。如果你在字典里看到这样的词条，你一定会生气。然而，数学中确实有很多概念是自己定义的。例如，n()的阶乘定义如下：n的阶乘等于n乘以n-1的阶乘。如果这样定义的话，恐怕就和上面的条目一样了：n-1的阶乘是多少？是 n-1 乘以 n-2 的阶乘。那么n-2的阶乘是多少？它永远不会就这样结束。因此，需要定义最关键的基本条件（Base Case）：0的阶乘等于1。

0!=1

n!=n·(n-1)!

因此，3!=3*2!、2!=2*1!、1!=1*0!=1*1=1。由于 Base Case，我们不会无休止地计算。知道了？ 1!=1，我们倒过来数一下，2!=2*1!=2*1=2, 3!=3*2!=3*2=6。我们用一个程序来完成这个计算过程。我们需要编写一个函数来计算阶乘。首先写出最简单的Base Case：

int factorial(int n)
{
	if (n == 0)
		return 1;
}

如果参数n不为0会发生什么？根据定义，应该是n*(n-1);。为了方便下面的分析，我们引入几个临时变量来分割这条语句：

int factorial(int n)
{
	if (n == 0)
		return 1;
	else {
		int recurse = factorial(n-1);
		int result = n * recurse;
		return result;
	}
}

这个函数实际上可以调用它自己吗？是的。直接或间接调用自身的函数称为递归函数。这里是直接调用自身。有时函数A调用函数B，函数B调用函数A。即函数A间接调用自身。这也是一个递归函数。如果您感到困惑，您可以将步骤 (n-1) 视为调用另一个函数 - 具有相同函数名称和相同代码的另一个函数。调用它就意味着跳转到它的代码处执行，然后返回(n-1)次调用的下一步继续执行。我们以（3）为例来分析整个调用流程，如下图所示：

图5.2.(3)调用流程

递推函数的单调性_函数的递推调用_什么是函数的递推调用

图中，实线箭头代表调用，虚线箭头代表返回。右边的方框代表了每层函数调用在调用和返回过程中存储空间的变化。

main() 有一个局部变量，由一个框表示。

调用(3)时，需要分配参数和局部变量的存储空间，因此main()下面多了一个框来表示(3)的参数和局部变量，其中n已初始化为3。

(3)再次调用(2)，分配(2)的参数和局部变量，因此main()和(3)下又多了一个框。如上所述，每次调用函数时都会分配参数和局部变量的存储空间，并在函数退出时释放它们的存储空间。 (3)和(2)是两个不同的调用。 (3)的参数n和(2)的参数n各有自己的存储单元。虽然我们在写代码的时候只写了一次参数n，但是运行时它并没有改变。是两个不同的参数n。并且由于(2)调用时(3)还没有退出，所以两个函数调用的参数n同时存在，所以在原来的基础上多画了一个盒子。

以此类推，请读者根据图自行分析整个调用过程。读者会发现，这个过程和前面我们用数学公式计算3!的过程是一样的。它们一步步展开，然后又一步步缩回。

我们看一下上图右侧存储空间的变化过程。随着函数调用越来越深入，一端的存储空间逐渐变大，然后随着函数调用一层层返回，这一端的存储空间逐渐缩短，而每次访问参数和局部变量时，可以只能访问此端的存储单元，不能访问内部存储单元。例如，当(2)的存储空间位于末尾时，只能访问其参数和局部变量，而不能访问(3)。 ) 和 main() 参数和局部变量。这种性质的数据结构称为栈或堆栈（Stack）。随着函数调用和返回而不断变化的一端称为栈顶。每个函数调用的参数和局部变量的存储空间（上图中的每个小盒子）称为栈帧。操作系统为程序的运行预留了一个堆栈空间。当函数调用时，栈帧就被分配在这个栈空间中，当函数返回时，栈帧被释放。

当编写递归函数时，如何证明它是正确的？像上面那样跟踪函数的调用和返回过程是一种方法，但是光是（3）就已经这么麻烦了。如果是（100）怎么办？虽然我们已经证明了（3）是正确的，但由于它与用数学公式计算是相同的过程和相同的结果，所以这不能代替（100）的证明。你该怎么办？对于其他函数，你可以跟踪它的调用过程来证明它的正确性，因为每个函数只调用一次并返回，但对于递归函数，遵循它只会让你头大。事实上，并不是每个函数调用都需要深入研究。当我们调用它时，我们没有深入了解它是如何打印的。我们只是相信它能够正确打印并完成它的工作，然后继续编写下面的代码。上一节我们写了和area函数，然后马上测试证明这两个函数是正确的，然后我们在写的时候调用了这两个函数：

return area(distance(x1, y1, x2, y2));

在写这句话的时候，我们是否需要深入到area函数中来知道我们是否正确调用了它？不，因为我们已经相信这两个函数可以正确工作，也就是说，我们相信如果我们将坐标传递给它，它将返回正确的距离，如果我们将半径传递给面积，它将返回正确的面积，所以我们叫他们来完成它。另一件作品也应该是正确的。这种“信念”被称为“信仰之跃”，即首先相信某些结论，然后用它们来证明其他结论。

编写(n)的代码时，在这个地方写：

...
int recurse = factorial(n-1);
int result = n * recurse;
...

这时候，如果我们认为(n-1)是正确的，也就是说，如果我们认为如果传递n-1，就会返回(n-1)！，那么就是(n-1)！，那么就是n*(n -1)!，也就是n!，这正是我们要返回的(n)的结果。当然这有点奇怪：我们还没有写完这个函数，为什么我们应该相信(n-1)是正确的呢？但信仰之跃本身就是跳跃，不是吗？如果你相信你正在写的递归函数是正确的，调用它，然后根据它写出递归函数，那么它就是正确的，并且值得你相信它是正确的。

这话说起来似乎有点神秘。让我们严格地从数学上证明该函数的正确性。正如我刚才所说，(n)的正确性取决于(n-1)的正确性。只要后者是正确的，那么后面的结果乘以n并返回这一步显然没有任何疑问，那么我们的函数实现就是正确的。。因此，证明(n)的正确性就是证明(n-1)的正确性。同理，证明(n-1)的正确性就是证明(n-2)的正确性，以此类推。，最后：证明(1)的正确性就是证明(0)的正确性。 (0)的正确性不依赖于其他函数调用。是程序中的一个小分支1；这个1是根据阶乘的定义写的，一定是正确的。因此，(1)的实现是正确的，因此(2)也是正确的，依此类推，最后(n)也是正确的。其实这就是我中学时学过的数学归纳法（）。使用数学归纳法证明，只需要证明两点：Base Case正确，递归关系正确。在写递归函数的时候，一定要记得写一个Base Case，否则即使递归关系正确，整个函数也不会正确。如果函数错过了基本情况：

int factorial(int n)
{
	int recurse = factorial(n-1);
	int result = n * recurse;
	return result;
}

那么这个函数就会一直被调用，直到操作系统为程序保留的堆栈空间耗尽，程序崩溃（分段错误）。这称为无限递归()。

到目前为止，我们只学习了所有 C 语法的一小部分，但现在我们应该告诉你：这个子集是完整的，本身就可以用作编程语言。 C语言有很多特性我们以后还要学习。但一切都可以用这些已经学过的功能来代替。换句话说，你以后要学习的C语言特性会让写代码变得更容易，但它们并不是必需的。现在你所学到的已经完全涵盖了第一节“程序和编程语言”中的五个基本指令。有些读者会说还没有讨论循环。是的，循环将在下一章中讨论，但一个重要的结论是递归和循环是等价的。所有可以用循环完成的事情都可以用递归完成，反之亦然。同样，事实上有些编程语言（比如一些LISP实现）只有递归而没有循环。计算机指令可以做的所有事情都是数据访问、操作、测试和分支、循环（或递归）。用高级语言编写的在计算机上运行的程序最终必须翻译成指令。指令不能做的事情是用高级语言编写的。程序肯定做不到。高级语言虽然有丰富的语法特征，但只是比指令编写起来更方便而已。他们可以做同样数量的事情。那么为什么计算机要这样设计呢？在设计时，您认为计算机应该如何具备这些功能，而不是或多或少的功能？这都要归功于早期的计算机科学家，比如艾伦，他们在计算机诞生之前就从数学理论中为计算机的设计指明了方向。例如，有兴趣的读者可以参考计算理论方面的教科书。

递归不仅仅是为了解决一些棘手的数学问题而想出来的技巧，它是计算机和编程语言的本质。我们在学习C的语法时见过很多递归的定义。例如，在提到的语法规则中，“表达式”是递归定义的：

表达式 → 表达式（参数列表）

参数列表 → 表达式、表达式、...

再比如，上面提到的俚语规则中，“”也是递归定义的：

语句→if（控制表达式）语句

可见，编译器在解析我们写的程序时，也必须使用大量的递归。请参考编译器的实现原理。

锻炼

1. 编写一个递归函数来查找两个正整数 a 和 b 的最大公约数 (GCD, )，使用以下算法：

如果a能被b整除，那么最大公约数就是b。

否则，最大公约数等于b和a%b的最大公约数。

该算法很容易证明。要求读者证明为什么可以通过这样的计算来计算出最大公约数。最后，修改您的程序以处理所有整数，而不仅仅是正整数。

2. 编写一个递归函数来查找序列的第 n 项。该序列定义如下：