第3章 递归

本章内容包括：

基本递归

一种强大的方法，允许一个问题以其自身越来越小的形式来定义自己。在计算机科学领域中，我们通过使用递归函数来解决带有递归性质的问题，也就是用函数调用自身。

尾递归

递归的一种形式，这里编译器会为此产生优化的代码。大多数现代的编译器能够识别尾递归。为此，只要条件允许我们都应该利用这个特性。

基本递归

假设想计算整数n的阶乘，比如4！=4×3×2×1。

迭代法：循环遍历其中的每一个数，然后与它之前的数相乘作为结果再参与下一次计算。可正式定义为：n! = (n)(n-1)(n-2)…(1)。

递归法：将n!定义为更小的阶乘形式。可以正式定义为：

递归过程中的两个基本阶段：递推与回归。

递推阶段，每一个递归调用通过进一步调用自己来记住这次递归过程。当其中有调用满足终止条件时，递推结束。每一个递归函数都必须拥有至少一个终止条件；否则，递推阶段就永远不会结束了。一旦递推阶段结束，处理过程就进入回归阶段，在这之前的函数调用以逆序的方式回归，直到最初调用的函数返回为止，此时递归过程结束。

示例3-1：以递归方式计算阶乘的函数实现

为理解递归究竟是如何工作的，有必要先看看C语言中函数的执行方式。基于这点，我们需要了解一点关于C程序在内存中的组织方式。

基本上来说一个可执行程序由4个区域组成：代码段、静态数据区、堆与栈（见图3-2a）。

代码段：包含程序运行时所执行的机器指令；

静态数据区：包含在程序生命周期内一直持久的数据，比如全局变量和静态局部变量；堆：包含程序运行时动态分配的存储空间，比如用malloc分配的内存；

栈：包含函数调用的信息。

按照惯例，堆的增长方向为从程序低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况可能不是这样，与CPU的体系结构有关）。

注意：此处的堆与数据结构中的堆没有什么关系。

图3-2：a）C程序在内存中的组织形式  b）一份活跃记录

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息。每一个调用都被当做是活跃的。栈上的那块存储空间称为活跃记录，或者称为栈帧。

栈帧由5个区域组成（见图3-2b）：

输入参数：传递到活跃记录中的参数

返回值空间：

计算表达式时用到的临时存储空间：

函数调用时保存的状态信息：

输出参数：传递给在活跃记录中调用的函数所使用的参数。

一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用产生的活跃记录将一直存在于栈中直到这个函数调用结束。

回到示例3-1，考虑一下当计算4!时栈中都发生了些什么。

初始调用fact会在栈中产生一个活跃记录，输入参数n=4（见图3-3，第1步）。

由于这个调用没有满足函数的终止条件，因此fact将继续以n=3为参数递归调用。这将在栈上创建另一个活跃记录，但这次输入参数（见图3-3，第2步）。这里，n=3也是第一个活跃期中的输出参数，因为正是在第一个活跃期内调用fact产生了第二个活跃期。

这个过程将一直继续，直到n的值变为1，此时满足终止条件，fact将返回1（见图3-3，第4步）。

图3-3：递归计算4!时的C程序的栈

算法精解（C语言描述） 第3章 读书笔记（待补）,布布扣,bubuko.com

算法精解（C语言描述） 第3章 读书笔记（待补）