发表于 2018-11-08 08:11:11   |   已被 访问: 292 次   |   分类于:   C语言   |   暂无评论

不知道大伙学习 C 语言感觉最难的是什么，反正我当初学习 C 语言时，觉得最难的就是“递归”了，比指针还难理解（C 语言中的指针，很多人都认为难以理解）。

那什么是“递归”呢？我有一天翻词典时，看到词典这么解释一个词：

惊人的：用来形容惊人的形容词。

这要么是恶搞，要么就是玩笑。然而在数学上确实有很多概念是用自己定义的，举个例子：n 的阶乘等于 n 乘以 n-1 的阶乘，并且 0 的阶乘等于 1。咋一看，似乎它并没有说清楚什么是阶乘，但是这样的描述，却足以让人知道怎样计算阶乘。例如计算 4 的阶乘：

4! = 4 x 3! 
= 4 x 3 x 2! 
= 4 x 3 x 2 x 1! 
= 4 x 3 x 2 x 1 x 0! 
= 4 x 3 x 2 x 1 x 1 
= 24

并不用细究阶乘到底是什么，只需要按照定义去计算即可，当然，这种定义方式必须要有一个“基础条件”，比如阶乘的“基础条件”就是 0! = 1。如果没有“基础条件”，阶乘只会无限往下推，没有尽头。

C 语言中，什么是递归函数

说了半天阶乘，就是为“递归”做铺垫的，如果一个概念需要用到自身，我们就称它的定义是递归的。那显然，递归函数一定是调用了自身的函数，这么说有点虚，来看看实例吧，下面用 C 语言计算 n 的阶乘。我们已经知道，递归最重要的就是“基础条件”了，我们先把阶乘的基础条件写好：

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

上面的代码实现了 0 的阶乘等于 1，那如果 n 大于 0 呢？按照阶乘的定义，应该是 n x fatorial(n-1)，用代码实现就是：

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

这就用 C 语言实现了计算 n 的阶乘。factorial 函数调用了自己，所以 factorial 是递归函数。事实上，不仅仅是直接调用自己，间接调用自己也属于递归函数。比如，A 调用了函数 B，函数 B 又调用了 A，那 A 也是递归函数。

那，递归函数是怎么执行的呢？

为了方便解释，我们在 factorial 函数的else 部分加几个局部变量：

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

这里以 factorial(3) 为例，用实线箭头表示调用，用虚线箭头表示返回，右边的框表示在调用和返回过程中各函数调用的局部变量的变化情况。

我们看图右边表示存储空间的框的变化过程，随着函数调用的层层深入，存储空间的一端逐渐增长，然后随着函数的层层退出，存储空间的这一端又逐渐缩短，这是一种具有特定性质的数据结构。它的特性就是只能在某一端增长或缩短，并且每次访问参数和局部变量时只能访问这一末端的单元，而不能访问内部的单元，比如当factorial(2)的存储空间位于末端时，只能访问它的参数和局部变量，而不能访问factorial(3)和main()的参数和局部变量。

具有这种性质的数据结构称为堆栈或栈（Stack）。每个函数调用的参数和局部变量的存储空间（图里的一个小方框）称为一个栈帧（Stack Frame）。系统为每个程序的运行预留了栈空间，函数调用时就在这个栈空间里分配栈帧，函数返回时就释放栈帧。

在我之前的文章《》也用到了“栈帧”的概念。

可以看出，写 C 语言递归函数最重要的就是一定要定义好“基础条件”，不然函数就会永远调用下去，知道系统资源耗尽程序崩溃为止。递归和循环是等价的，用循环能做的事用递归都能做，反之亦然，事实上有的编程语言（如某些LISP）只有递归而没有循环。

计算机硬件能做的所有事情就是数据存取、运算、测试和分支、循环（或递归），在计算机上运行的高级语言写的程序当然也不可能做到更多的事情，虽然高级语言有丰富的语法特性，但也只是为做这些事情提供一些方便。那么，为什么计算机是这样设计的？为什么想到计算机需要具有这几种功能，而不是更多或者更少？这些要归功于早期的计算机科学家，例如Alan Turing，他们在计算机还没有诞生的年代从数学理论上为计算机的设计指明了方向。

本文主要参考 linux C编程一站式学习。