C语言面试题详解(第12节)

指针是C语言中非常重要，也是相对比较难的语法，所以前面花了几节主要讨论了一些关于C语言指针的面试题目，相信对大家有一定的帮助。不过不知道大家如何，反正我当初学习C语言的时候，觉得最难的还不是指针，而是递归！

其实仔细想想，在C语言中，指针问题只是死板的语法问题，熟练掌握以后，一切都很简单。而递归则是一种思想，考察的是程序员的逻辑思维能力，可以简单，也可以非常复杂。即使是工作多年的程序员，碰到递归问题，觉得棘手也不是什么稀奇事。

事实上，递归问题常常是求职笔试或者面试题目中最为复杂的地方，由递归衍生出的相关问题，例如迭代、概率、循环等问题，也是招聘公司经常考察的点。本系列文章接下来，将尝试通过一些较为简单的案例，讨论遇到递归问题该如何考虑。

C语言中递归的基本概念

如果一个C语言函数调用了它自己，则就称该函数是递归函数。下面举一个最简单的实例：

利用递归编程计算 n 的阶乘。

要解决这个问题，首先要知道什么是“阶乘”。阶乘是数学中常用的计算，常用 n！ 表示 n 的阶乘。它在数学中的定义是：n 的阶乘等于 n-1 的阶乘，其中 n 是大于 0 的整数，0 的阶乘等于 1.

初次接触阶乘的朋友到这里可能还是有些迷惑：这就完了？用“阶乘”去定义阶乘？是的，阶乘的定义其实就是一种递归。不过虽然这句话没有解释出什么是阶乘，但我们已经可以计算出 n 的阶乘了。例如计算 4！：

3！ = 3*2！
= 3*2*1！
= 3*2*1*0！
= 6

现在尝试使用C语言编程解决该问题。显然，使用C语言的循环语句是非常容易写出计算阶乘的函数的，请看：

int factorial_loop(int n)
{
    int res = 1, i;
    for(i=1; i<=n; i++)
        res *= i;
    return res;
}

可以看出，上面C语言的循环语句其实是将计算阶乘的过程逐项展开了，而数学中阶乘的定义其实更像是一个递推公式。接下来将尝试使用C语言递归函数计算阶乘，请读者比较递归与循环方式的思想差异。

首先假设负责阶乘运算的是 factorial() 函数，那么显然，计算 n! 就等于 factorial(n)，并且 factorial(n) = n* factorial(n-1)，因此相应的C语言代码可以如下写：

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

这就完了吗？当然还没，上面这种写法只是默认 n 大于 0 的，n 等于 0 的情况还没有考虑呢。按照阶乘的定义，0! 等于 1，相关的C语言代码可以如下写：

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

因为当 n 等于 0 时，函数就直接返回了，所以 else 可以省去，因此 factorial() 函数最终可以如下定义：

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

比较 factorial_loop() 函数与 factorial() 函数之间的差异，相信读者应该能够看出，循环实现方式相当于把阶乘的各个阶段展开，而递归方式则是严格按照阶乘的数学定义实现的。

以人类的思维来看，循环方式更像是逐项展开的“笨方法”，而递归方式则优雅一点，是按照数学定义递推出来的。当然了，对于计算机来说，循环和递归都是计算，从某种程度上来说，二者是等价的。

那么，factorial() 函数是如何执行的呢？该如何分析它呢？

分析C语言递归函数的方法

一般编程教材在分析C语言中的递归函数时，仅会从编程语言的角度去分析，而这么分析又常常比较复杂，导致初学者困惑不已，甚至对递归产生畏惧心理。以上面的 factorial() 函数为例，为了便于分析，对 factorial() 函数添加若干中间变量，修改后的C语言代码如下：

#include <stdio.h>
 int factorial(int n)
{
     if(0==n)
         return 1;
     int recurse = factorial(n-1);
     int result = n*recurse;
     return result;
}
int main()
{
     int result = factorial(3);
     printf("%d\n", result);
     return 0;
} 

假设在 main() 函数中调用 factorial() 函数，并传入参数 3。那么，factorial(3) 的计算过程是怎样的呢？看了第5节内容的朋友应该明白，在C语言中，每发生一次函数调用，就涉及到一次栈帧的分配，那么在计算 factorial(3) 时，调用关系和栈帧分配与返回回收是如下进行的：

上图是从编程语言的角度解释 factorial(3) 计算过程的，显然，这么分析太痛苦了，而且 factorial() 函数属于非常简单的递归函数，要是递归函数再复杂些，还利用这种方法分析就太难了。

事实上，如果抛开编程语言，仅从实际问题出发来分析 factorial() 函数，就非常简单了。factorial() 函数其实就是将n！ 的数学公式，以C语言的形式重新表达了一遍而已。

再来看一个例子

C语言中的递归函数一般都不是通过仔细推敲堆栈设计的，那样太麻烦了，递归其实是用来减轻程序员的工作的。例如编写C语言代码计算阶乘时，若是使用递归函数，程序员甚至都无需彻底弄懂什么是阶乘，只需要使用C语言把阶乘的数学定义描述一遍就可以了。

下面再来看一个例子，这个问题来自台湾某杀毒软件公司的面试题：

利用递归编写C语言函数 void print_str(char* str)，将字符串 str 逐字节输出。

要是以逆向分析堆栈的方式解决这个问题，就太难了。所以，我们不分析堆栈，直接使用C语言描述这个问题即可。首先，我们已知 print_str() 函数是将字符串逐字节输出的，也就是一次只输出一个字节，使用C语言描述这一过程是简单的：

void print_str(char* str)
{
    printf("%c\n", *str);
}

再读一遍题目，应该能够发现要求是“逐”字节输出字符串的，所以在输出字符串中的某一个字节后，还要输出下一个字节，这一过程利用C语言描述也是简单的：

void print_str(char* str)
{
    printf("%c\n", *str);
    print_str(str+1);
}

这就完了吗？当然没，C语言中字符串是以'\0'结尾的，遇到它就应该结束 print_str() 函数了，所以最终 print_str() 函数的C语言代码如下：

void print_str(char* str)
{
    if('\0' == *str)
        return;
    printf("%c\n", *str);
    print_str(str+1);
}

可以看出，这样从实际意义出发编写C语言递归函数就非常简单了。编写 main() 函数调用 print_str() 函数，发现一切与预期一致：

 int main()
{
     char str[] = "hello world";
     print_str(str);
     return 0;
 }

“C语言递归函数”，其实可以从“C语言”和“递归”两种角度去理解。不过，从本文可以看出，若仅从编程语言的角度去理解递归，就太复杂了。递归考察的并不是程序员对堆栈理解的熟练程度，而是解决问题的一种思想。