下载掌阅APP，畅读海量书库
立即打开
递 归过程的执行总是一个过程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行……如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分……如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合“逐步深入，而后又逐步返回”的递归调用模型，以解决实际的面试例题。
在程序设计面试中，一个能够完成任务的解决方案是最重要的，解决方案的执行效率要放在第二位考虑。因此，除非试题另有要求，你应该从最先想到的解决方案入手。如果它是一个递归性的方案，你不妨向面试官说明一下递归算法天生的低效率问题，表示你知道这些事情。有时候你同时想到两个解决方案：递归的和循环的，并且实现方式差不多，你可以把两个都向考官介绍一下。
面试例题1： 把一个数组里的数组合全部列出，比如1和2列出来为1,2,12,21。[日本著名软件公司S2007年面试题]
解析： 本题考查的是循环递归算法。
答案： 代码如下。
面试例题2： 试用递归的方法编程计算菲波那契数列的通项f(n)，已知f1=1，f2=1，以后每项都是前两项的和。[中国大陆著名杀毒软件公司J2005，2009年面试题]
解析： 本题的考点是递归问题。
答案： 代码如下。
面试例题3： 一个字符串中可能包含a～z中的多个字符，如有重复，如String data="aavzcadfdsfsdhshgWasdfasdfdddaaa"，求出现次数最多的那个字母及次数，如有多个重复的则都求出。[中国大陆著名杀毒软件公司J2007年面试题]
解析： 主要思路如下。
（1）引入TreeSet：通过集合快速找到所有出现的字符串。
（2）引入ArrayList：为了快速排序，再通过StringBuffer生成排序后的字符串。
（3）通过String api中的基本方法indexOf lastIndexOf来计算TreeSet中每个字符串的最大值。
（4）如果出现相同的，则把相同的都记录在一个列表中。
（5）记录第一个出现次数最多的字符（为了计算多个字符串相同情况）。
（6）计算最大字符串列表中哪些才是真正出现次数最多的。
答案： 代码如下。
面试例题4： 利用1、2、2、3、4这5个数字，用Java写一个main函数，打印出所有不同的排列，如12234、21234等，要求打印出来的不能有重复。[中国大陆著名杀毒软件公司J2007年面试题]
解析： 这道题的难点在于如何消减重复的2。对于任意一个串利用递归进行排列时，循环串中的每个字符到第一个字符进行递归。如果串中字符出现重复，则重复的字符只可以利用递归算法一次，即只要与前面相同的字符循环到第一个字符时，不调用递归就可以避免重复。
答案： 代码如下。
面试例题1： 下列程序的输出结果是什么？[中国大陆某软件公司Y2009年9月笔试题]
A.Hello world B.Hello C.编译错误 D.以上答案都不对
解析： 局部变量声明的作用范围是在一个块内，也可以理解为在“{}”内。for循环可以不使用“{}”的，但仅限于执行语句（其中并不包括变量声明语句），由于这段代码中Integer k的作用范围在整个main方法中，这样就造成了变量重复定义的错误。所以，在编译时会出错。若要改正，只要加上一对花括号，让变量声明在块内就可以，代码如下所示：
这道题目告诉我们在编写代码时尽量使用标准的语句，哪怕循环体内只有一行，也最好用花括号括起来，以免产生歧义。
答案： C
面试例题2： Consider a function which,for a given whole number n,returns the number of ones required when writing out all numbers between 0 and n.
For example,f（13）=6.Notice that f（1）=1.What is the next largest n such that f（n）=n?（解释：有一个整数n，写一个函数f（n），返回0～n之间出现的“1”的个数。比如f（1）=1；f（13）=6（1、10、11、12、13一共6个1），问一个最大的f（n）=n中的n是什么？）[美国著名搜索引擎公司G2009年12月笔试题目]
解析： 这个题目的关键在效率上，在没有发现很科学、快速地计算出个数的情况下，可以采用缓存的机制。因为就200000来说，计算时间已经无法忍受了，因此，可以把前面的计算结果缓存下来，把每次的结果保存好，就不用每次都重新计算，从而可提高效率。例如，计算101，只要把之前1～100的结果与101相加就行了。
答案： 代码如下。
面试例题3： Which of the choices below correctly describes the amount of time used by the following code?（下面哪个选项正确地描述了代码运行的调度次数？）
A.Θ(n^3) B.Θ(n2logn) C.Θ(n(log n)*2) D.Θ(n log n)
解析： 本题考查面试者对时间复杂度的理解。本题涉及如下概念。
1 .时间频度
一个算法执行所耗费的时间从理论上是不能算出来的，必须上机运行测试才知道。但不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了，并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。
2 .时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，引入了时间复杂度的概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记为T（n）=O（f（n）），称O（f（n））为算法的渐进时间复杂度，简称时间复杂度。
在各种不同的算法中，若语句的执行次数为一个常数，则时间复杂度为O(1)，另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1，它们的频度不同，但时间复杂度相同，都为O(n^2)。
按数量级递增排列，常见的时间复杂度有：
随着规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
3 .算法的时间复杂度
若要比较不同的算法的时间效率，受限要确定一个度量标准，最直接的办法就是将计算法转化为程序，在计算机上运行，通过计算机内部的计时功能获得精确的时间，然后进行比较。但该方法受计算机的硬件、软件等因素的影响，会掩盖算法本身的优劣，所以，一般采用事先分析估算的算法，即撇开计算机软硬件等因素，只考虑问题的规模（一般用自然数n表示），认为一个特定的算法的时间复杂度只采取于问题的规模，或者说它是问题的规模函数。
为了方便比较，通常的做法是，从算法中选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的，基本操作的执行次数实际上就是相应语句的执行次数。
一般来说：
所以，要选择时间复杂度量级低的算法。
至于本题，从代码可知，x=x+1;是循环最内侧代码，其时间复杂度最高，所以只求这句代码的复杂度即可。从内到外看，k循环从1==2^0开始每次变成原来的2倍，一直到大于n-1，所以，循环体运行次数是|log（n）|，时间复杂度为O（log（n））（计算机中log默认底数是2）；j循环从1开始每次递增n/2，一直到n-1，第一次递增之后，j变成（n+2）/2,第二次递增j，则是n+1。所以应该是循环了2次，但是时间复杂度还是O（1）,因为常数次数的时间复杂度都是O（1）的，i循环从1开始，每次增1，一直到n-1，所以循环体运行n-1次，时间复杂度O（n）。最后相乘得到总的时间复杂度就是O（n*1*log（n））=O（n*log（n））。这里要强调一下，时间复杂度都不带常数项或者常数系数的，所以不存在所谓O（2n）这样的时间复杂度。
答案： D
面试例题4： 如何利用筛选法查找100以内的素数？[英国著名图形软件公司面试题]
解析： 首先定义a[i]=1，初始化整个数组，全部初始化为1，第二步双重循环，从2开始，所有2的倍数都标记为0，所有3的倍数也标记为0；然后是4，但因为4已经被标记为零了，跳过；接着是5，直到所有的数都循环过一遍。
答案： 代码如下。
扩展知识：变量的内存分配情况
求素数的方法不止一种，下面是用开根号的办法求值，也可以达到目的，代码如下。
