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语言”和“递归”两种角度去理解。不过,从本文可以看出,若仅从编程语言的角度去理解递归,就太复杂了。递归考察的并不是程序员对堆栈理解的熟练程度,而是解决问题的一种思想。

阅读更多:   C语言
添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif