参考：http://www.nowamagic.net/librarys/veda/detail/2314
递归的感悟:
1、 保留当前的状态，开一个平行时空，寻找不同的可能性。
2、 反复对某一数组进行修饰，直到满意
递归相对于循环的优势，就是它的两个步骤递和归，虽然对于空间性的消耗是可怕的，但是它却能在”递”中找不到结果的时候，通过”归”返回到之前的结果。
递归需要满足的条件：l 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。
l 存在一种简单情境，可以使递归在简单情境下退出。
递归和循环的区别：1、 递归消耗更多的运行时间和空间，因为存在变量入栈的情况。但是在面对如汉诺塔这样的模型，递归能更好地解决
2、 递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘的递归实现与循环实现。）
归纳法：
归纳法的实质们从求解一个带有参数的相同问题开始，将其推广到包含所有n个物体。也就是通过找到index索引和我们最终要得到结果的一个相关关系，并用数学公式的形式表示出来。
归纳法感觉是比较基础的东西。
这里我们常用到的主要有：
排序算法方法：选择排序 、插入排序
基数排序对：
7467 6792 9134 9123 1239
3245 7823 9871 8765 6743
进行排序。
整数幂以及多项式求值寻找多数元素（数量要在[n/2]）分治：把问题实例划分若干实例（多数情况分成两个），并分别递归地解决每个实例，然后把这些子实例的解组合起来，得到原问题实例的解。
寻找最大最小值算法：MINMAX：
输入；n个整数的数组A[1-n]n为2的幂
输出；(x,y),A中的最大的元素和最小元素
1.minmax(1,n)
过程：min(low,high)
1. if high – low =1 then
2. ifA[low] < A[high] then return (A[low],A[high])
3. elsereturn(A[high],A[low])
4. end if
5. else
6. mid =[(low + high) / 2]
7. (x1,y2)=minmax(low,mid)
8. (x2,y2)=minmax(mid+1,high)
9. x = min{x1,x2}
10. y = max{y1,y2}
11. return (x,y)
12. end if
eg：
二分搜索：
算法：BINARYSEARCH
输入；非降序排列的n个元素的数组A[1…n]
输出；如果x=A[j]，则输出j，否则输出0
1. binarysearch(1,n)
过程：binarysearch(low,high)
1.if low >high then return 0
2.else
3. mid =[(low+ high)]
4. if x =A[mid] then return mid
5. else if x< A[mid] then return binarysearch(low,mid-1)
6. elsereturn binarysearch(mid+1,high)
7. end if
自底向上排序：
算法：MERGESORT
输入；那个元素的数组A[1…n]
输出；按照非降序排列数组A[1..n]
1.mergesort（A,1,n）
过程：mergesort(low,high)
1. if low < high
2. mid =[(low + high)/2]
3. mergesort(A,low,mid )
4. mergesort(A,mid+1,high)
5. Merge(A,low,mid,high)
6. end if
MERGE
输入：数组A[1..m]和它的三个索引p,q,r, 1<=p<=q<r<=m，两个子数组A[p..q]和A[q+1...r]各自按升序排列。
输出：合并两个子数组A[p..q]和A[q+1..r]的数组A[p..r]
1、 B[p..r]是个辅助数组
2、 s = p;t = q+1; k = p
3、 while s <= q and t <= r
4、 if A[s]<= A[t] then
5、 B[k] = A[s]
6、 s= s+1
7、 else
8、 B[k]= A[i]
9、 t= t+1
10、 end if
11、 k = k+1
12、 end while
13、 if s = q+1 then B[k..r] =A[t..r]
14、 else B[k..r] = A[s..q]
15、 end if
16、 A[p..r] = B[p..r]
寻找第K小元素
SELECT
输入：n个元素数组A[1..n]和整数k，1<=k<=n
输出：A中的第k小元素
1. select(A , 1 , n, k)
过程：select(A,low,high,k)
1.p= high – low + 1
2.ifp < 44 then 将A排序return(A[k])
3. 将A分成q组，每组5个元素。如果5不整除 p，则排除剩余的元素
4.将q组中的每一组单独排序，找出中项。所有中项的集合为M
5.mm= select(M, 1, q, [q/2]) {mm为中相机和的中项}
6.将A[low..high]分成三组
A1= {a|a<mm}
A2= {a|a==mm}
A3= {a|a>min}
7. case
|A1|>=k :return select(A1, 1, |A1| , k)
|A1| + |A2|>= k: return mm
|A1|+|A2|<k:return select(A3, 1, |A3| , k - |A1|-|A2|)
8. end cas
动态规划不同于分治算法的直接实现地推结果不同，动态规划导致了不止一次的递归调用，因此这种技术采用自底向上的方式地递推求值，并把中间结果存储起来以后用来计算所需要求的解。利用这种技术可以设计出特别有效的方法来解决多组合最优问题。
动态规划过程：
每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划三要素：
（1）问题的阶段
（2）每个阶段的状态
（3）从前一个阶段转化到后一个阶段之间的递推关系。
斐波那契数列
可以理解为：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。
当n为1时，f(n) = 1,n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。
1.procedure f(n)
2.if ( n =1) or (n = 2) then return 1
3.else return f(n-1) + f(n-2)
斐波那契数列只是给我们展示了动态规划的大概意思，实际上完全可以用以下代替：
F[0] = 0;F[1] = 1;
for(i = 2; i <=N; i++)
F[i] = F[i-1] + F[i-2];
只需要保存前两个值就基本上搞定了
无论是动态规划，还是分治，或者是他们的基础递归，感觉还有很大空间去理解~