递归与分治策略（一）
简而言之，递归就是自己调用自己。
递归算法：直接或者间接地调用自身的算法。
递归函数：用函数自身给出定义的函数。
注意：每个递归函数都必须有非递归定义的初始值，以确保递归函数完成计算。
下面通过两个例子来介绍递归的特点
例1阶乘函数
阶乘函数递归地定义为：
n!=1(n=0)
或者
n!=n(n-1)!(n>0)
下面用一段简单的Java代码实现
这里是递归实现：
public static int facterial(int n) {if (n == 0)return 1;else if (n < 0)return -1;//发生异常，退出elsereturn n * facterial(n – 1);}
下面是迭代实现：
public static int f(int n) {if (n == 0)return 1;else if (n < 0)return -1;//发生异常，退出else {for (int i = n – 1; i >= 1; i–) {n *= i;}return n;}}
分析比较一下两种实现方法：
比较可知两种实现的时间复杂度等价，空间复杂度递归占用的略大一下，但是代码的结构清晰度递归更清晰一些。
下面进行第二个例子的讲解
例2Fibonacci数列
Fibonacci数列的递归定义为
F(n)=1(n=0,1)
或者
F(n)=F(n-1)+F(n-2)(n>1)
下面用一段简单的Java代码实现
这里是递归实现：
public static int fibonacci(int n ){if(n<0)return -1; //发生异常，退出else if(n<=1)return 1;elsereturn fibonacci(n-1)+fibonacci(n-2);}
下面是迭代实现：
public static int F(int n){if(n<0)return -1; //发生异常，退出else if(n<=1)return 1;else {int f0=1,f1=1,fx=0;for(int i=2;i<=n;i++){fx=f0+f1;f0=f1;f1=fx;}return fx;}}
分析比较一下两种实现方法：
比较可知递归实现的时间复杂度已经非常大了，空间复杂度递归占用的略大一下，但是代码的清晰度递归更清晰一些。而真正使用起来递归实现的代码是无用代码，用n=40这个数测试一下便知，，递归实现的耗时太长了，有兴趣的可以测试一下。
下面归纳一下递归算法的特点：
1.简单（结构清晰，可读性强）
2.性能较低（相比较迭代而言）
性能较低的原因有以下两点：
1需递归调用工作栈支持（无法避免）
2有可能出现子问题重叠现象（必须尽力避免）
这里递归的主要知识点就讲完了，下面介绍一下文章标题的分治法。
分治法的基本思想：
分解：讲一个大规模的问题分解为多个规模较小的子问题，需要注意的是子问题必须互相独立并且与原问题相同。
这里用一个例子进行讲解：归（合）并排序。
这里留在下一篇文章介绍，睡觉咯，今天学到了这些，和大家分享一下，感谢大家的支持。
我们什么都没有，唯一的本钱就是青春。
