到这里，本讲差不多要结束了，最后我们再想一个问题，就是既然二分查找法效率这么高，甩线性查找法好多条街，那为什么还要线性查找法呢？

其实，线性查找法也不是一无是处，它最大的优点就是简单，特别简单，傻瓜式的。你不是让我找东西吗，好啊，那我就把我兜里所有的东西一个一个拿出来看看有没有，是不是很傻瓜式哈~

还有一点就是二分法本身也有局限性，那就是二分法必须要求待查数组是已排序的，比如我给你一个很大的数组，但是这个数组并没有排序，那你如果想用二分查找法的话还必须先给数组排序，然后再查找。这样就会造成除查找之外的额外成本（排序），至于这个额外成本是不是可承受的，就要看开发者自己权衡了，搞不好还不如线性查找快呢。

算法效率比较

线性查找：查找次数平均为N/2.

二分查找：查找次数在10位的数组中最大数为4（运气好的好，也许第一次就找到了）。那么这样看，线性查找只是比二分查找多了一次查找而已，并没有看出二分查找的优势。

当数组的基数放大时，线性查找次数将会成正比增长，K=N/2；

二分查找，我们通过一个公式来表达，K=㏒2(N),对数计算给出了二分查找法最大耗费的次数。

线性查找在最坏的情况下，其效率是O(n);而二分查找的效率是O(logn),其效率是以存储结构为代价的。

第五讲 递归算法

什么是递归，以编程的角度来看，程序调用自身的编程技巧称为递归（ recursion）。

记得小时候经常听的一个故事：从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容是“从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容......”

　　递归做为一种算法在程序设计语言中广泛应用。 一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

　　递归，就是在运行的过程中调用自己方法或函数。

　　递归必须要有三个要素：

　　①、边界条件

　　②、递归前进段

　　③、递归返回段

　　当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

1. 求一个数的阶乘：n!

n! = n*(n-1)*(n-2)*......1

n!=n*(n-1)!

(n-1)!=(n-1)*(n-2)!

规定：

　　①、0！=1

　　②、1！=1

　　③、负数没有阶乘

上面的表达式我们先用for循环改写：

如果求阶乘的表达式是这样的呢？

n! = n*(n-1)！

我们用递归来改写：