下载掌阅APP，畅读海量书库
立即打开
递 归问题通常是求职笔试中最为复杂的地方，也是本书的难点之一。由递归衍生出的相关问题，诸如迭代问题、概率问题、循环问题也是企业经常重复的考点。在阅读本章之前，请读者参考数据结构经典书籍对递归基础知识做简要复习。本章将通过对各公司面试题目进行全面仔细的解析，帮助读者解决其中的难点。
递归是程序设计中的一种算法。一个过程或函数直接调用自己本身或通过其他的过程或函数调用语句间接地调用自己的过程或函数，称为递归过程或函数。递归是计算机语言中的一种很有用的工具，很多数学公式用到递归定义，例如 N ！：当 n >0时， f （ n ）= n × f （ n -1）。
有些数据结构（如二叉树），其结构本身就有递归的性质。有些问题本身没有明显的递归结构，但用递归求解更简单。
递归是较难理解的算法之一。简单地说，递归就是编写这样一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程如下图所示。
递归过程的执行总是一个过程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行，……，如此反复，不断深入，直到某次过程的执行时终止递归调用的条件成立，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行余下的部分，……，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程程序设计的核心就是参照这种执行流程，设计出一种适合“逐步深入，而后又逐步返回”的递归调用模型，以解决实际问题。
递归算法应该包括递归情况和基底情况两种情况。递归情况演变到最后必须达到一个基底。
在程序设计面试中，一个能够完成任务的解决方案是最重要的，解决方案的执行效率要放在第二位考虑。因此，除非试题另有要求，应该从最先想到的解决方案入手。如果它是一个递归性的方案，不妨向面试官说明一下递归算法天生的低效率问题——表示你知道这些事情。有时候同时想到两个解决方案：递归的和循环的，并且实现方式差不多，可以把两个都向考官介绍一下。比如 N ！问题，利用循环语句解释就是：
不过，如果用循环语句做的改进算法实现起来要比递归复杂得多的话——大幅度增加了复杂度而在执行效率上得不到满意的回报，我们建议还是优先选择递归来解决问题。
面试例题1： 递归函数mystrlen（char*buf，int N）是用来实现统计字符串中第一个空字符前面字符长度。举例来说：
字符串buf，当输入N=10或者20，期待输出结果是6；当输入N=3或5，期待输出结果是3或5。
What are all the possible mistakes in the code?（代码中可能的错误是哪个/些）
A.There are no mistakes in the code（没错）
B.There is no termination of recursion（没有递归退出条件）
C.Recursion cannot be used to calculate this function（递归是不能实现这个函数的功能）
D.The use of N/2 in the recursion is incorrect（对N/2的使用是错误的）
解析 ：递归函数关注以下几个因素：退出条件，参数有哪些？返回值是什么？局部变量有哪些？全局变量有哪些？何时输出？会不会导致堆栈溢出？本题中递归函数显然没有退出条件。
答案：B
扩展知识：下面是该递归函数的正确实现方法
面试例题2： Find the number of different shortest paths from point A to point B in a city with perfectly horizontal streets and vertical avenues as shown in the following figure.No path can cross the fenced off area shown in gray in the figure.
A.11
B.15
C.17
D.19
E.20
解析 ：此题中想要最短距离到达B点，所有行走路径，从起点出发后只能→或↓，任何←和↑都将增加路径长度。
在不存在阻碍的情况下，假设在任意 M，N 的此种格子上，从左上A出发到右下B的不同走法有 f（M，N）种，则根据递推可知 f（M，N）=f（M-1，N）+f（M，N-1），等号右边两项分别对应在当前点向下走一步和向右走一步的情况。递归终止情况为：
f（M，0）==f（0，N）==0 和 f（1，1）==1。
对于题目中有阻碍的情况，如下：
从A出发到X点的不同走法数为f（4，2），到达X点后只有1种走法，即一直向右到B。
从A出发到Y点的不同走法数为f（2，4），到达后再到B点的不同走法数为f（3，2），因此连接的总数为f（2，4）*f（3，2）。
至此，唯一没有涵盖的走法为经Z点至B点，此种走法有且只有1种。
因此总数目为 f（4，2）+f（2，4）*f（3，2）+1==17。
答案 ：C
面试例题3： An algorithm starts with a single equilateral triangle and on each subsequent iteration add new triangles all around the outside.The result for the first three values of n are shown following figure.How many small triangles will be there after the 100 iterations?
A.19800
B.14501
C.14851
D.14702
E.15000
解析 ：本题规律如下，新增加的小三角形数目为3*（n-1）。
答案 ：C
面试例题1 ：If we define F（0）=0，F（1）=1，F（n）=F（n-1）+F（n-2）（n>=2），what is the result of F（1025）mod 5?[美国著名操作系统软件企业M公司2013年面试题]
A.0 B.1 C.2 D.3 E.4
解析 ：这里是对递归函数取余，所以我们最好先做一下拆项：
所以F（1025）mod 5=3*F（1020）mod 5；
依此类推：
F（5）为5，mod后值为0。所以F（1025）mod 5=0；
答案： A
面试例题2 ：请给出此题的非递归算法：
[中国著名门户网站企业S公司2008年6月面试题]
解析 ：本题类似于杨辉三角形，其实就是计算一个对角线值，用list保存一个对角线元素即可。除了横边和纵边按顺序递增外，其余每一个数是它左边和上边数字之和。
如上所示，假如想求 m 为3、 n 为4的 f （ m ， n ）值，就是25。
答案： 代码如下：
面试例题3 ：设计递归算法 x（x（8））需要调用几次函数x（int n）。[美国著名数据分析软件企业SA公司2009年11月面试题]
解析： 单计算x（x（8））的值自然是9，但是本题要考查的是调用了几次x函数。可以把x（8）理解为一个二叉树。树的节点个数就是调用次数：
x（8）的结果为9；x（x（8））也就是x（9）的二叉树形如：
节点数为9，也就是又调用了9次函数。所以一共调用的次数是18次。
答案 ：18
面试例题1 ：以下代码的输出结果是什么？[中国著名金融企业J银行2008年面试题]
A.10，0，9，1
B.10，10，9，0
C.10，1，9，2
D.9，10，8，0
解析 ：for循环括号内被两个分号分为3部分：i=0是初始化变量；x>8是循环条件，也就是只要x>8就执行循环；那y=i++是什么？在第一次循环时执行了么？答案是不执行，y=i++实际上是个递增条件，仅在第二次循环开始时才执行。所以结果是10，10，9，0。
面试者务必要搞清楚下面程序和题目的不同点：
与题目不同，y=i++在循环体内，而不作为递增条件，所以在第一次循环就执行了，所以输出结果是10，0，9，1。
答案 ：B
面试例题2： 输入 n ，求一个 n × n 矩阵，规定矩阵沿45度线递增，形成一个zigzag数组（JPEG编码里取像素数据的排列顺序），请问如何用C++实现？[中国台湾著名硬件公司2007年11月面试题]
解析 ：在JPEG图形算法中首先对图像进行分块处理，一般分成互不重叠且大小一致的块，量化的结果保留了低频部分的系数，去掉了高频部分的系数。量化后的系数按zigzag扫描重新组织，然后进行哈夫曼编码。zigzag数组是一个“之”字形排列的数组。
答案 ：用C++编写完整代码如下：
面试例题3： 有两等长数组A、B，所含元素相同，但顺序不同，只能取得A数组某值和B数组某值进行比较，比较结果为大于、小于或等于，但是不能取得同一数组A或B中的两个数进行比较，也不能取得某数组中的某个值。写一个算法实现正确匹配（即A数组中某值与B中某值等值）。[英国著名图形图像公司A 2007年4月校园招聘面试题]
解析 ：算法：循环加判断可以很快地解决这个问题。算法分析：假设两个数组A[10]、B[10]。将A.0与B.0进行比较，判断它们是否等值或大于、小于，如果等值则打印出来，不等则比较B.1……依此类推。
答案：
代码如下：
扩展知识
我们这里用的循环加比较的算法可以很快地解决这个问题，但却并不是最优算法。如果笔试时间充足的话，我们可以对算法做某些优化。
建立一个结构数组C，结构为{某数在B中的位置，标记，某数在A中的位置}。其中“标记”可为大于、小于、等于。“某数在 A/B 中的位置”为 0～ n -1，这是相应位置。第一次比较后，C中元素都为{某数在B中的位置，标记，A0}格式。然后执行如下步骤：
（1）在A数组中随机选取一个数（根据题意，我们并不知道这个值的确定值是多少），比如说 A [ i ]，然后和B数组中的数进行比较。根据数据结构C，将B数组中每个数与 A [ i ]进行比较，若比 A [ i ]大，从后向前存储，比 A [ i ]小则从前向后存储，要是等于 A [ i ]，就记录下这个值在B的位置 j 。继续比较，直到B数组中的数全部比较完成，然后再把这个 b [ j ]插入空余的那个中间位置。
（2）然后再从A数组中取出数 A [ k ]{ k =0～ n }与 B [ j ]（这个 B [ j ]就是 A [ i ]，因为同一数组中不能比较大小，只能采用这种方式）比较，若比 B [ j ]大，那么从结构数组C中 A [ i ]后面比较，若比 B [ j ]小，就从结构数组C中 A [ i ]前面比较，直到找到相等的为止，然后更新结构数组C中与这个相等的相应值。注意，在这里，只更新相等的那个数值的“标记”，其他与 A [ k ]不相同（或大，或小）的情况下不更新，即还保持 A [ i ]的比较结果，以利于下一次进行比较。
（3）重复步骤（2），继续取A数组剩下的值，仍然与那个 B [ j ]比较，这样逐步更新结构数组C，直到A数组全部取出比较完，那么这个程序也就完成了相应的功能。
这里用到了快速排序和二分法的某些思想。选择合理的 A [ i ]，可以大大降低比较次数。
面试例题4 ：The following C++code tries to count occurence of each ASCII charcaterin given string and finally print out the occurrency numbers.（下面C++代码用来统计每个ASCII字符的出现次数，最后给出出现数值。）
If there may be some issue in the code above，which line（s）would be?（如果上面代码有错，将在哪行出现，如何修改？）
答案 ：这段代码有两个错：
（1）hist[*src]++；这一行应该修改为hist[*src++]++；这是因为在while（*src！='\0'）循环体是看*src的值是否为'\0'来作为结束的。所以src必须递加。否则hist[*src]其实就是hist['a']，'a'会隐式转换成97也就是hist[97]++不停递加，进入死循环。
（2）for（i=0；i<=256；i++）这一行应该修改为for（i=0；i<=255；i++），否则会超界。
面试例题5 ：设计一个定时器程序，当输入一个时间，就按照输入值停留多少。[美国著名软件公司I2013年笔试题]
解析 ：可以用Sleep来控制时间，并用双精度传值作参数传递。
答案：
面试例题1： 看清以下数字排列的规律，设1点的坐标是（0，0）， x 方向向右为正， y 方向向下为正。例如，7点的坐标为（-1，-1），2点的坐标为（0，1），3点的坐标为（1，1）。编程实现输入任意一点坐标（ x ， y ），输出所对应的数字。[芬兰某著名软件公司2005年面试题]
解析 ：规律能看出来，问题就在于如何利用它。很明显这个队列是按顺时针方向螺旋向外扩展的，我们可以把它看成一层一层往外延伸。第0层规定为中间的那个1，第1层为2到9，第2层为10到25。1、9、25……不就是平方数吗？而且是连续奇数（1、3、5……）的平方数。这些数还跟层数相关。推算一下就可以知道，第 t 层之内共有（2 t -1） 2 个数，因而第 t 层会从[（2 t -1） 2 ]+1开始继续往外螺旋伸展。给定坐标（ x ， y ），如何知道该点处于第几层？层数 t =max（| x |，| y |）。
知道了层数，接下来就好办多了，这时我们就知道所求的那点一定在第 t 层这个圈上，顺着往下数就是了。要注意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同。可以分成4种情况——上、下、左、右或者东、南、西、北，分别处于4条边上进行分析。
● 东|右：x==t，队列增长方向和 Y 轴一致，正东方向（y=0）数值为（2t-1）^2+t，所以v=（2t-1）^2+t+y。
● 南|下：y==t，队列增长方向和 X 轴相反，正南方向（x=0）数值为（2t-1）^2+3t，所以v=（2t-1）^2+3t-x。
● 西|左：x==-t，队列增长方向和 Y 轴相反，正西方向（y=0）数值为（2t-1）^2+5t，所以v=（2t-1）^2+5t-y。
● 北|上：y==-t，队列增长方向和 X 轴一致，正北方向（x=0）数值为（2t-1）^2+7t，所以v=（2t-1）^2+7t+x。
其实还有一点很重要，不然会有问题。其他3条边都还好，但是在东边（右边）那条线上，队列增加不完全符合公式。注意到东北角（右上角）是本层的最后一个数，再往下却是本层的第一个数，当然不满足东线公式。所以我们把东线的判断放在最后（其实只需要放在北线之后就可以了），这样一来，东北角那点始终会被认为是北线上的点。
答案 ：代码如下：
扩展知识（有时公司还会考类似的面试题如下）
如矩阵：
找出规律，并打印出一个 N × N 的矩阵；规律就是从首坐标开始顺时针依次增大，代码如下：
面试例题2 ：输入一个n，输出2到n的具体素数值[美国某著名企业2012年10月面试题]
答案 ：代码如下：
面试例题1 ：Please write out the program output.（写出下面程序的运行结果。）[德国某著名软件咨询企业2005年10月面试题]
解析 ：这是我所见到的概率面试例题中出得非常好的一道。
从表面上看，你完全无法看出它是一个概率问题。这里暗含的思想是一个1/4圆和一个正方形比较大小的问题，如右图所示。
RAND_MAX是随机数中的最大值，也就是相当于最大半径 R 。 x 和 y 是横、纵坐标上的两点，它们的平方和开根号就是原点到该点（ x ， y ）的距离，当然这个距离有可能大于R，如 b 点，还有可能小于 R ，如 a 点。整个题目就蜕化成这样一个问题：随机在正方形里落1000个点，落在半径里面的点有多少个。如果落在里面一个点，则累积一次。
那这个问题就很好解决了，求落点可能性之比，就是求一个1/4圆面积和一个正方形面积之比。
1/4圆面积=（1/4）×π× r × r ；正方形面积= r × r
两者之比=π/4；落点数=π/4×1000=250×π≈ 785
答案 ：出题者的意思显然就是要求你得出一个大概值，也就是250×π就可以了。实际上呢，你只要回答700～800之间都是正确的。
我们算的是落点值，落点越多，越接近250×π，落10个点、100点都是很不准确的，所以该题落了1 000个点。读者可以上机验证该程序，将Loop改成10 000、100 000来试验，会发现结果越来越接近250×π。