数据结构与算法(5.递归方法论)

06 Aug 2022 in Posts / Algorithm

数据结构与算法(5.递归方法论)

• 0. 递归衍变
• 1. 自下而上
• 2. 自上而下
• 参考

0. 递归衍变

1. 普通递归: 自下而上
2. 尾递归(优化内存堆栈): 自上而下(附带中间参数)
3. 循环

招式:

1. 基本情况, 即跳出条件
2. 递推关系, 即相关变量计算, 也是中间变量处理
3. 循环判断基本情况, 优化成循环

1. 自下而上

1. 寻找递归递推关系
2. 寻找递归基本情况，跳出时返回基本情况的结果
3. 修改递归函数的参数
4. 递归调用并返回中间变量
5. 使用递归函数的返回值与当前参数进行计算，并返回最终结果

返回值 f(参数) {
    if (基本情况条件) return 基本情况的结果;       
    
    修改参数；
    返回值 = f(参数); 
    
    最终结果 = 根据参数与返回值计算
    return 最终结果;
}

2. 自上而下

1. 寻找递归递推关系
2. 创建新函数，将「自下而上」中的最终结果计算依赖的中间变量提取为函数的参数
3. 寻找递归基本情况，跳出时返回基本情况的结果与中间变量的计算结果（最终结果）
4. 根据函数参数与中间变量重新计算出新的中间变量
5. 修改参数
6. 递归调用并返回（该处的返回由基本情况触发）

返回值 f(参数，中间变量) {
    if (基本情况条件) return 基本情况的结果与中间变量的计算结果;
    
    中间变量 = 根据参数与中间变量重新计算
    修改参数；
    
    return f(参数,中间变量);
}

参考

• 如何轻而易举的写出递归函数