证明数据结构分析中的结论的两个常用的方法时归纳法和反证法
归纳法：第一步是证明基准情形，就是确定定理对于某个小的值的正确性，（这一步几乎是很简单的
第二部，进行归纳假设，一般来说，这意味着假设定理对直到某个有限数k的所有的情况都成立的，然后使用这个假设证明定理对于下一个值也是成立的。
反证法：通过假设定理不成立，然后证明该假设导致某一个已知性质不成立，从而说明原假设是错误的。
反证法和归纳法不同处，归纳发从基础出发，反证法从结论出发。
什么是递归：当一个函数用他自己来定义时就称为是递归。
不是所有的数学递归都能有效的由c的递归模拟来实现。（如果c中的递归没有基准情况，也是毫无意义的）
递归调用将反复进行直到基准情形出现。
编写递归程序的时候，关键是记牢递归四条基本法则：
1 基准情形 （总有某些基准情形，它无需递归就能解出）
2 不断推进 （对于那些需要递归求解的情形，每次递归调用都必须要使求解状况朝接近基准情形方向推进）
3 设计法则 （假设所有的递归调用都能运行）
4 合成效益法则。（在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作）
（有时候不需要递归，如果使用了递归，则记住第四条，合成效益）
原文：http://www.cnblogs.com/ccccccccc/p/3753197.html