跳转至

4.1 递归和循环

和数据结构一样, 考查算法的面试题也备受面试官的青睐. 有很多算法都可以用递归和循环两种方式实现. 通常递归实现的代码比较简洁, 但性能却不如基于循环的实现方法, 在面试的时候, 可以根据题目的特点, 甚至可以和面试官讨论选择合适的方法编程.

通常排序和查找是面试时考查算法的重点. 在准备面试的时候, 我们应该掌握二分查找, 归并排序和快速排序, 做到能随时正确, 完整的写出代码.

如果在面试题要求写出二维数组(可能具体表现为迷宫或者棋盘等) 上搜索路径, 那么我们可以尝试用回溯法. 通常回溯法很适合用递归的代码实现. 只有当面试官限定不可以用递归实现的时候, 我们在考虑用栈来模拟递归的过程.

如果面试题是求某个问题的最优解, 并且该问题可以分为多个子问题, 那么我们可以尝试用动态规划. 在用自上而下的递归思路去分析动态规划问题的时候, 我们会发现子问题之间存在重叠的更小子问题, 为了避免不必要的重复计算, 我们用自下而上的循环代码来实现, 也就是把子问题的最优解算出来并用数组保存下来, 接下来基于问题的解计算大问题的解
如果我们告诉面试官动态规划的思路之后, 面试官还在提醒说在分解子问题的时候是不是存在某个特殊的选择,如果采用这个特殊的选择将一定能得到最优解, 那么, 通常面试官这样的提示意味着该问题可能适用于贪婪算法, 当然面试官也会要求应聘者证明贪婪算法选择的确最终能够得到最优解

位运算可以看成一类特殊的算法, 它是把数字表示成二进制之后对0 和 1的操作. 由于位运算的对象为二进制数字, 所以不是很直观, 但掌握它也不难, 因为总共只有 与, 或, 异或, 左移, 右移5中位运算.

递归和循环

如果我们需要重复多次计算相同问题时, 可以选择递归或循环, 面试时, 如果面试官没有特别要求, 尽量多采用递归的方法实现

递归的缺点:

  • 递归虽然有简洁的优点, 但由于递归调用函数自身, 而函数调用是有时间和空间消耗的, 每一次函数调用, 都需要在内存栈中保存分配空间以保存参数, 返回地址和临时变量, 而且往栈里压入输入和弹出数据都需要时间.
  • 递归有可能很多计算是重复的, 从而对性能带来很大的负面影响, 递归的本质是把一个问题分解成两个或多个小问题, 如果多个小问题存在相会重叠的部分, 就存在重复计算. (面试题10, 60)
  • 可能引起调用栈溢出问题.

面试题10: 斐波那契数列

Question

求斐波那契数列的第n项, 写一个函数, 输入n, 求斐波那契数列的第n项, 斐波那契数列的定义如下

Tip

方法1: 时间复杂度O(2^n) 递归,很多C语言教科书在讲述递归函数的时候,都会用斐波那契数列作为例子,因此很多应聘者对递归解法都很熟悉,很快写下了代码:

long Fibo1(unsigned int n)
{
    if (n <= 1)
        return n;
    return Fibo1(n - 1) + Fibo1(n - 2);
}
面试官会提示我们上述递归的解法有很严重的效率问题并要求我们分析原因。 我们以求解f(10)为例,要求得f(10), 要先求得f(9)和f(8)... 我们可以用树形结构来表示这种依赖关系

方法2: 时间复杂为O(n) 我们不能发现,这棵树种有很多节点是重复的,而且重复的节点数会随着n的增大而急剧增加,这意味着计算量会随着n的增大而急剧增大。 其实改进的方法并不复杂,上述递归代码之所以慢,是因为重复计算太多,我们只要想办法避免重复计算就行了,比如我们可以把已经得到的数列中间项保存起来,在下次需要计算的时候先查找一下,如果前面已经计算过了就不用再重复计算了。

更简单的办法是重下往上计算,首先根据f(0)和f(1)计算除f(2),以此类推,时间复杂为O(n)

long Fibo2(unsigned int n)
{
    if (n <= 1)
        return n;

    int FiboOne = 0;
    int FiboTwo = 1;
    int FiboN = 0;

    for (size_t i = 2; i <= n; i++)
    {
        FiboN = FiboOne + FiboTwo;
        FiboOne = FiboTwo;
        FiboTwo = FiboN;
    }
    return FiboN;
}    

Answer

完整代码: Fibo

测试用例

  • 功能测试,输入 3, 5, 10等
  • 边界值测试 输入 0, 1, 2等
  • 性能测试 输入较大的数 40, 50, 100等

本题考点

  • 递归,循环的理解及编码能力
  • 时间复杂度分析的能力
  • 数学建模的能力