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

为什么要研究“递归”

递归并不算是C语言的语法，更像是程序设计中的一种算法，从某种程度上来说，递归过程其实就是实现自我嵌套的过程，理解这一过程要求程序员具备一定的逻辑思维能力。当然了，使用合适的方法，对理解复杂递归过程也是有一定的帮助的。因此，上一节在讨论了C语言中的递归函数时，介绍了设计和理解递归的两种方法，相信对读者有一定的帮助。

上一节在介绍如何从C语言角度分析递归函数时，相信读者也注意到了，递归函数在返回之前总是在申请栈空间的，也就是说，如果C语言的递归函数没有在栈空间被消耗完返回，就会导致整个C程序的崩溃。那为什么还要研究递归呢？请看下面这段C语言代码：

struct list{
    struct list *next;
    int val;
};

显然，这个结构体可以定义出C语言程序开发中常用的数据结构——链表。相信大家能够看出，链表也算是一种递归。

其实，不仅仅是C语言，在基于其他任何编程语言的程序开发中，递归都是一个很重要的思想，也非常能锻炼程序员的逻辑抽象思维能力。作为程序员，应该能从实际案例中学到提升自己的东西，这样才不至于成为只会 if else 编程的程序员。

当有问题需要解决时，最先考虑的肯定是解决问题的方法，但是如果问题是递归的，则应该考虑使用循环语句是否也一样方便，毕竟，递归算法天生具有低效率问题。不过，递归在处理一些递推逻辑时具备循环无法比拟的优势，所以有时在C语言程序开发中，使用循环语句比使用递归语句复杂的多，这时究竟使用循环还是递归，就看程序员自己的取舍了。

来看看这个面试题

下面这个题目来自美国某著名软件M公司的面试题，请看：

C语言递归函数 mystrlen(char * buf， int N) 是用来统计字符串中第一个空字符前面字符长度的，例如有

char buf[] = {'a', 'b', 'c', 'd', 'e', 'f', '\0', 'x', 'y', 'z'};

期望 mystrlen(buf, 20) 返回 6，mystrlen(buf, 3) 返回 3，为此如下编写了递归函数 mystrlen() 的C语言代码如下：

int mystrlen(char* buf, int N)
 {
     return mystrlen(buf, N/2) + mystrlen(buf+N/2, N/2);
}

问：上述 mystrlen() 函数的C语言代码存在什么问题？

• A. 函数没有问题
• B. 函数没有定义退出条件
• C. 递归是不能实现这个函数功能的
• D. 对 N/2 的使用时错误的

本节开头就提到，“递归过程其实就是实现自我嵌套的过程”以及“如果C语言的递归函数没有在栈空间被消耗完返回，就会导致整个C程序的崩溃”，那显然，上面 mystrlen() 函数属于C语言中的递归函数，但是却没有定义函数的退出条件，答案很明显是 B。

那么答案有没有可能是 C 或者 D 呢？也就是说，mystrlen() 函数不能使用 N/2 实现，或者更进一步，可能它就根本没法使用递归实现？肯定不是啊，当然可以用 N/2 拆分，将 mystrlen() 定义为递归函数，并实现它应有的功能。

那递归函数 mystrlen() 该如何实现呢？

如何理解和设计C语言中的递归函数，上一节已经较为详细的讨论，这里我们就直接使用上一节介绍的方法，请继续往下看。

首先，假设 mystrlen() 函数已经能够解决需求了。那 mystrlen(buf, 0) 显然应该等于 0，这一过程使用 C语言描述是简单的，请看：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    ...
}

当 N 大于 0 时，还有一种可能 mystrlen() 会输出 0，就是 buf 的第一个字符就等于 '\0'，因此也要将其写入C语言代码：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    if('\0'==*buf)
        return 0;
    ...
}

这个就是C语言中递归函数所谓的“退出条件”了。因为要考虑 mystrlen() 函数的第二个参数 N，一个比较好的办法就是把 N 拆分成若干个小片段做进一步分析。而面试题的 D 选项提到“使用 N/2 错误了”，所以为了证明 D 选项是错误的，这里对 N 做二等分，先使用 mystrlen() 函数分析前半段字符串，C语言代码如下：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    if('\0'==*buf)
        return 0;
    int tmp = mystrlen(buf, N/2);
    ...
}

tmp 就是字符串 buf 前面 N/2 长度内，在题目制定的规则下的长度。到这里，应该考虑到 N 是 int 型的整数，所以既然以“N/2”的方式拆分字符串，N=1 这种情况应做特殊考虑。因为如果 buf 的第一个字符不是 '\0'，而 N = 1，mystrlen() 函数就应该输出 1 才对，所以相关 C 语言代码可以如下写：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    if('\0'==*buf)
        return 0;
    if(1==N)
        return 1;
    int tmp = mystrlen(buf, N/2);
    ...
}

继续分析，如果 tmp 小于 N/2，就说明 '\0' 出现在字符串 buf 前 N/2 里，后面的 N/2 就不用再判断了，此时 mystrlen() 函数可以直接返回，相关C语言代码可以如下定义：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    if('\0'==*buf)
        return 0;
    if(1==N)
        return 1;
    int tmp = mystrlen(buf, N/2);
    if(tmp<N/2)
        return tmp;
    ...
}

否则就说明 '\0' 出现在 buf 的后 N/2 里，因此应将 tmp 与接下来 N/2 的 buf “面试题规则下的”长度相加，也即：

int mystrlen(char* buf, int N)
{
    if(0==N)
        return 0;
    if('\0'==*buf)
        return 0;
    if(1==N)
        return 1;
    int tmp = mystrlen(buf, N/2);
    if(tmp<N/2)
        return tmp;
    return tmp+mystrlen(buf, N/2);
}

到这里，mystrlen() 函数就应该能够实现面试题中的需求了吧。为了验证它，我们写 main() 函数调用该函数：

编译并执行这段C语言代码，得到如下结果：

# gcc t.c
# ./a.out 
2 4

怎么回事？！输出不应该是 3 6 吗？

为什么 mystrlen() 函数得到了错误的结果

在编写递归函数 mystrlen() 的C语言代码时，我们的分析应该都一切正确啊，那怎么没有得到正确结果呢？在之前的文章中，我一直在强调基础的重要性，基础不牢，就很容易写出有隐患的代码。在调试不正常工作的程序时，甚至会对问题代码视而不见，这里就是一个例子。

那为什么 mystrlen() 函数没输出正确结果呢？在回答这问题之前，先来考虑这个问题：

在C语言中，int 型变量 N 会一直等于 N/2 + N/2 吗？

显然不会。若N为奇数，N 就不再等于 N/2 + N/2 了。和数学不太一样，若 N 是 int 型变量，则 N 应始终等于 N/2 + (N+1)/2。这就明白为什么我们定义的 mystrlen() 函数没能正确输出答案了，也知道怎样修改相关的C语言代码了，请看：

如果将 “N 与 N/2 + N/2 问题”单拿出来，相信又会有朋友说是“扣字眼”的无聊基础题了，不过你看，如果不重视这样的问题，确实会写出问题代码的。

本节首先分析了美国某著名软件M公司的面试题给出的C语言代码存在的问题，然后又一点一点的写出了递归函数。容易看出，在编写递归函数C语言代码的过程中，我们并不是推敲堆栈关系，来设计和实现C语言递归函数的，而是通过“递归逻辑思维”逐步分析问题并写出代码的。

从本专栏的第一节开始，就总是有朋友回复说研究这些“古怪的”的面试题没有意义，因为实际开发中根本用不到，或者根本不让用（遵循某些开发规范）。但是，本专栏从来都不是为了做题而做题，也并不是推崇这些题中的“奇技淫巧”，而是通过某些比较有意思的案例，介绍C语言中的基础知识，以及程序开发中的一些思维。