• 好好学习,天天向上~
  • 欢迎欢迎~

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

c语言 lcc 239℃ 0评论

为什么要研究“递归”

递归并不算是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语言中的基础知识,以及程序开发中的一些思维。


C语言面试题详解(第13节) - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (0)分享 (0)
发表我的评论
取消评论
表情     9 + 0 = ? (必填)