那些年,面试中常见的数据结构基础和算法题(下) (10)

前面总结了随机算法,这次再把以前写的递归算法的文章梳理一下,这篇文章主要是受到宋劲松老师写的《Linux C编程》的递归章节启发写的。最能体现算法精髓的非递归莫属了,希望这篇文章对初学递归或者对递归有困惑的朋友们能有所帮助,如有错误,也恳请各路大牛指正。二叉树的递归示例代码请参见仓库的 binary_tree 目录,本文其他代码在 这里。

1.递归算法初探

本段内容主要摘自《linux C一站式编程》,作者是宋劲松老师,这是我觉得目前看到的国内关于Linux C编程的最好的技术书籍之一,强烈推荐下!

关于递归的一个简单例子是求整数阶乘,n!=n*(n-1)!,0!=1 。则可以写出如下的递归程序:

int factorial(int n) { if (n == 0) return 1; else { int recurse = factorial(n-1); int result = n * recurse; return result; } } 复制代码

factorial这个函数就是一个递归函数,它调用了它自己。自己直接或间接调用自己的函数称为递归函数。如果觉得迷惑,可以把 factorial(n-1) 这一步看成是在调用另一个函数--另一个有着相同函数名和相同代码的函数,调用它就是跳到它的代码里执行,然后再返回 factorial(n-1) 这个调用的下一步继续执行。

为了证明递归算法的正确性,我们可以一步步跟进去看执行结果。记得刚学递归算法的时候,老是有丈二和尚摸不着头脑的感觉,那时候总是想着把递归一步步跟进去看执行结果。递归层次少还算好办,但是层次一多,头就大了,完全不知道自己跟到了递归的哪一层。比如求阶乘,如果只是factorial(3)跟进去问题还不大,但是若是factorial(100)要跟进去那真的会烦死人。

事实上,我们并不是每个函数都需要跟进去看执行结果的,比如我们在自己的函数中调用printf函数时,并没有钻进去看它是怎么打印的,因为我们相信它能完成打印工作。 我们在写factorial函数时有如下代码:

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)是正确的?如果你相信你正在写的递归函数是正确的,并调用它,然后在此基础上写完这个递归函数,那么它就会是正确的,从而值得你相信它正确。

这么说还是有点玄乎,我们从数学上严格证明一下 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) 也是正确的。

其实这就是在中学时学的数学归纳法,用数学归纳法来证明只需要证明两点:Base Case 正确,递推关系正确。写递归函数时一定要记得写 Base Case,否则即使递推关系正确,整个函数也不正确。如果 factorial 函数漏掉了 Base Case,那么会导致无限循环。

2.递归经典问题

从上一节的一个关于求阶乘的简单例子的论述,我们可以了解到递归算法的精髓:要从功能上理解函数,同时你要相信你正在写的函数是正确的,在此基础上调用它,那么它就是正确的。 下面就从几个常见的算法题来看看如何理解递归,这是我的一些理解,欢迎大家提出更好的方法。

2.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。

/** * 汉诺塔 */ void hano(char a, char b, char c, int n) { if (n <= 0) return; hano(a, c, b, n-1); move(a, c); hano(b, a, c, n-1);

}

void move(char a, char b)
{
printf("%c->%c\n", a, b);
}
复制代码

2.2)求二叉树的深度

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzwzjs.html