递归面试题汇总"/>
递归面试题汇总
一、前言
找工作面试时最喜欢问的是算法题,虽然我觉得有些取巧的算法题只是跟刷题量有关。但是为了找工作不得不加强算法,特别是基础算法,这是一个人基本功的体现。《算法导论》是不错的教材,不过大部头看起来确实需要发时间,到现在还只是大略看了一遍,很多推导过程没细心看下来,深以为憾,以后有时间还是要猛补。算法题中最能体现算法精髓的则非递归莫属了,我对递归一直总觉得是一知半解,为了加深自己的理解,决定把自己的一些想法记下来,方便更好的理清自己的思路,也恳请各路大牛指正。
二、递归算法初探
本段内容素材来自《linux C一站式编程》,作者是宋劲松老师,说实话这是目前看到的国内关于linux C编程的最好的一本技术书籍,强烈推荐!
关于递归的一个简单例子是求整数阶乘,n!=n*(n-1)!,0!=1 。则可以写出如下的递归程序:
[cpp] view plain copy
- int factorial(int n)
- {
- if (n == 0)
- return 1;
- else {
- int recurse = factorial(n-1);
- int result = n * recurse;
- return result;
- }
- }
factorial
这个函数就是一个递归函数,它调用了它自己。自己直接或间接调用自己的函数称为递归函数。这里的factorial
是直接调用自己,有些时候函数A调用函数B,函数B又调用函数A,也就是函数A间接调用自己,这也是递归函数。如果觉得迷惑,可以把factorial(n-1)
这一步看成是在调用另一个函数--另一个有着相同函数名和相同代码的函数,调用它就是跳到它的代码里执行,然后再返回factorial(n-1)
这个调用的下一步继续执行。
为了证明递归算法的正确性,我们可以一步步跟进去看执行结果。记得刚学递归算法的时候,老是有丈二和尚摸不着头脑的感觉,那时候总是想着把递归一步步跟进去看执行结果。递归层次少还算好办,但是层次一多,头就大了,完全不知道自己跟到了递归的哪一层。比如求阶乘,如果只是factorial(3)跟进去问题不大,但是若是factorial(100)那就麻烦了。
事实上,我们并不是每个函数都需要跟进去看执行结果的,比如我们在自己的函数中调用printf函数时,并没有钻进去看它是怎么打印的,因为我们相信它能完成打印工作。我们在写factorial函数时有如下代码:
[cpp] view plain copy
- ...
- int recurse = factorial(n-1);
- int result = n * recurse;
- ...
这时,如果我们相信factorial是正确的,那么传递参数为n-1它就会返回(n-1)!,那么result=n*(n-1)!=n!,从而这就是factorial(n)的结果。
当然这有点奇怪:我们还没写完factorial
这个函数,凭什么要相信factorial(n-1)
是正确的?可Leap of Faith本身就是Leap(跳跃)的,不是吗?如果你相信你正在写的递归函数是正确的,并调用它,然后在此基础上写完这个递归函数,那么它就会是正确的,从而值得你相信它正确。
这么说好像有点儿玄,我们从数学上严格证明一下factorial
函数的正确性。刚才说了,factorial(n)
的正确性依赖于factorial(n-1)
的正确性,只要后者正确,在后者的结果上乘个n
返回这一步显然也没有疑问,那么我们的函数实现就是正确的。因此要证明factorial(n)
的正确性就是要证明factorial(n-1)
的正确性,同理,要证明factorial(n-1)
的正确性就是要证明factorial(n-2)
的正确性,依此类推下去,最后是:要证明factorial(1)
的正确性就是要证明factorial(0)
的正确性。而factorial(0)
的正确性不依赖于别的函数调用,它就是程序中的一个小的分支return 1;
这个1是我们根据阶乘的定义写的,肯定是正确的,因此factorial(1)
的实现是正确的,因此factorial(2)
也正确,依此类推,最后factorial(n)
也是正确的。其实这就是在中学时学的数学归纳法(Mathematical Induction),用数学归纳法来证明只需要证明两点:Base Case正确,递推关系正确。写递归函数时一定要记得写Base Case,否则即使递推关系正确,整个函数也不正确。如果factorial
函数漏掉了Base Case,那么会导致无限循环。
三、递归算法题
从上一节的一个关于求阶乘的简单例子的论述,我们可以了解到递归算法的精髓:要从功能上理解函数,同时你要相信你正在写的函数是正确的,在此基础上调用它,那么它就是正确的。下面就从几个常见的算法题来看看如何理解递归,这是我的一些理解,欢迎大家提出更好的方法。
1)汉诺塔问题
汉诺塔问题是个常见问题,就是说有n个大小不等的盘子放在一个塔A上面,自底向上按照从小到大的顺序排列。要求将所有n个盘子搬到另一个塔C上面,可以借助一个塔B中转,但是要满足任何时刻大盘子不能放在小盘子上面。
基本思想分三步,先把上面的N-1个盘子经C移到B,然后将最底下的盘子移到C,再讲B上面的N-1个盘子经A移动到C。总的时间复杂度f(n)=2f(n-1)+1,所以f(n)=2^n-1。
[cpp] view plain copy- void hano(char a, char b, char c, int n) {
- if (n > 0) {
- hano(a, c, b, n-1);
- move(a, c);
- hano(b, a, c, n-1);
- }
- }
- void move(char a, char b)
- {
- cout << a << "->" << b << endl;
- }
2)求二叉树的深度
这里的深度指的是二叉树从根结点到叶结点最大的高度,比如只有一个结点,则深度为1,如果有N层,则高度为N。[cpp] view plain copy
- int depth(struct node* root)
- {
- if (root == NULL)
- return 0;
- else {
- int lDepth = depth(root->left); //获取左子树深度
- int rDepth = depth(root->right); //获取右子树深度
- return lDepth>rDepth? lDepth+1: rDepth+1; //取较大值+1即为二叉树深度
- }
- }
注意Base Case,这里就是当root==NULL时,则深度为0,函数返回0。
3)判断二叉树是否平衡
一颗平衡的二叉树是指其任意结点的左右子树深度之差不大于1。判断一棵二叉树是否是平衡的,可以使用递归算法来实现。[cpp] view plain copy
- bool is_balanced(BinaryTreeNode* pRoot)
- {
- if(pRoot == NULL) //基本情况,为空的话,返回true
- return true;
- int left = depth(pRoot->m_pLeft);
- int right = depth(pRoot->m_pRight);
- int diff = left - right; //计算左右子树深度之差
- if(diff > 1 || diff < -1) //如果深度之差大于1返回false
- return false;
- return is_balanced(pRoot->m_pLeft) && is_balanced(pRoot->m_pRight); //递归判断左右子树,注意是&&,即左右子树都必须是平衡的这棵二叉树才是平衡的
- }
上面代码性能不高,会重复遍历结点,一个改进的算法是采用后序遍历的方式遍历树的结点,在遍历到本结点前我们已经遍历完了它的左右子树,我们只需要在遍历的时候记录结点的深度,就可以一边遍历一边判断该结点是否是平衡的。代码如下: [cpp] view plain copy
- bool is_balanced_2(BinaryTreeNode* pRoot, int* pDepth)
- {
- if(pRoot == NULL)
- {
- *pDepth = 0;
- return true;
- }
- int left, right;
- if(is_balanced_2(pRoot->m_pLeft, &left) //左子树平衡
- && is_balanced_2(pRoot->m_pRight, &right)) //右子树平衡
- {
- int diff = left - right;
- if(diff <= 1 && diff >= -1)
- {
- *pDepth = 1 + (left > right ? left : right);
- return true;
- }
- }
- return false;
- }
调用的函数定义如下: [cpp] view plain copy
- bool IsBalanced(BinaryTreeNode* pRoot)
- {
- int depth = 0;
- return is_balanced_2(pRoot, &depth);
- }
4)排列算法
排列算法也是递归的典范,记得当初第一次看时一层层跟代码,头都大了,现在从函数功能上来看确实好理解多了。先看代码: [cpp] view plain copy- void perm(int a[], int k, int N) { //k为起始位置,N为数组大小
- if (k == N-1) {
- output(a, N); //输出排列
- } else {
- for (int i=k; i<N; i++) {
- swap(a, i, k); //交换
- perm(a, k+1, N); //下一次排列
- swap(a, i, k); //恢复原来的序列
- }
- }
- }
基础条件是k==N-1,此时已经到达最后一个元素,一次排列已经完成,直接输出。否则,从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换),然后进行下一次排列,排列完成后记得恢复原来的序列。 假定数组a大小N=3,则程序调用perm(a, 0, 3)可以如下理解: 第一次交换0,0,并执行perm(a, 1, 3),执行完再次交换0,0,数组此时又恢复成初始值。 第二次交换1,0(注意数组此时是初始值),并执行perm(a, 1, 3), 执行完再次交换1,0,数组此时又恢复成初始值。 第三次交换2,0,并执行perm(a, 1, 3),执行完成后交换2,0,数组恢复成初始值。 也就是说,从功能上看,首先确定第0个位置,然后调用perm(a, 1, 3)输出从1开始的排列,这样就可以输出所有排列。而第0个位置可能的值为a[0], a[1],a[2],这通过交换来保证第0个位置可能出现的值,记得每次交换后要恢复初始值。 如数组a={1,2,3},则程序运行输出结果为:1 2 3 ,1 3 2 ,2 1 3 ,2 3 1 ,3 2 1 ,3 1 2 。即先输出以1为排列第一个值的排列,而后是2和3为第一个值的排列。
5)组合算法
组合算法也可以用递归实现,只是它的原理跟0-1背包问题类似。即要么选要么不选,注意不能选重复的数。完整代码如下: [cpp] view plain copy- #include<iostream>
- using namespace std;
- #define N 3 //数组大小为3
- int select[N] = {0}; //选择数组,用于存储数组哪些数字被选中。
- /*输出数组中选中的数*/
- void output(int a[], int n)
- {
- for (int i=0; i<n; i++) {
- if (select[i])
- cout << a[i] << " ";
- }
- cout << endl;
- }
- /*数组a从位置i开始选取k个数*/
- void combination(int a[], int i, int k)
- {
- if (i > N) return; //位置超出数组范围直接返回,否则非法访问会出段错误
- if (k == 0) { //选取完了,输出选取的数字
- output(a, N);
- } else {
- select[i] = 1;
- combination(a, i+1, k-1); //第i个数字被选取,从后续i+1开始选取k-1个数
- select[i] = 0;
- combination(a, i+1, k); //第i个数字不选,则从后续i+1位置开始还要选取k个数
- }
- }
- /*组合主函数,包括选取1到n个数字*/
- void combination_helper(int a[], int n) {
- for (int k=1; k<=n; k++) {
- combination(a, 0, k);
- }
- }
- int main()
- {
- int a[N] = {1, 2, 3};
- combination_helper(a, N);
- return 0;
- }
更多推荐
递归面试题汇总
发布评论