递归算法总结"/>
数据结构和算法面试题系列—递归算法总结
这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在CSDN。现整理为一个系列给需要的朋友参考,如有错误,欢迎指正。本系列完整代码地址在 这里。
注:此刻,我正在从广州回家的绿皮火车上整理的这篇文章,火车摇摇晃晃,颠簸的尽是乡愁,忍不住又想翻翻周云蓬的《绿皮火车》了。———记于2018年9月30日夜22:00分。
0 概述
前面总结了随机算法,这次再把以前写的递归算法的文章梳理一下,这篇文章主要是受到宋劲松老师写的《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;
复制代码
<
更多推荐
数据结构和算法面试题系列—递归算法总结
发布评论