递归

关键词: 逆向思维 栈 树 递归树

递归一般分四步

1. 递归函数定义
   • 明确函数使命
   • 明确原问题与子问题
   • 兼顾原问题和子问题
2. 基础情况处理
   • 数据规模较小时候,直接返回答案
3. 递归调用
   • 超级操作
   • 看成整体,忽略细节,用数学归纳法推导是否成立
   • 相信它一定能完成使命
4. 递推到当前层
   • 微操作

int func(n)             // 1. 递归函数定义
{
    if n == 0 return 1; // 2. 基础情况处理
    tmp = func(n--);    // 3. 递归调用
    return tmp * n;     // 4. 递推到当前层
}

经典例子: 大象装冰箱,汉诺塔,阶乘,斐波那契数列,归并排序,

1 如何解决晕递归

1. 把递归调用当做一个整体,不要纠结内部调用.
2. 通过数学归纳法,推导出它一定能完成函数的使命

2 计算时间复杂度

概念: 节点的单一子问题代价: 函数执行过程中，除去递归调用以外的代价

算出单一节点的代价 O(?),算出节点个数为 n ,代价为 O(?)*n