04-递归与分治

type
status
date
slug
summary
tags
category
icon
password

递归

一个函数调用自身，直到达到一个终止条件（base case）。
  • 每一层调用会进入新的函数栈帧
  • 必须有明确的终止条件
  • 思想简单，代码简洁，但要防止栈溢出

分治

把一个大问题分解成若干个结构相同的子问题，分别解决后再合并结果。
  • Divide（分解）：将原问题划分成子问题；
  • Conquer（解决）：递归地解决每个子问题；
  • Combine（合并）：合并子问题的解，得到原问题的解。
  • 快速排序（Quick Sort）
    • 分解： 选一个基准值，把数组分成左右两部分
    • 解决： 对左右子数组分别递归排序
    • 合并： 不需要合并，分治中完成排序
  • 归并排序（Merge Sort）
    • 分解： 拆成左右两半
    • 解决： 递归排序左右
    • 合并： 将两个有序数组合并成一个
  • 二分查找（Binary Search）
    • 分解： 每次只查一半
    • 解决： 在左或右子数组递归查找
    • 合并： 不需要合并
对比项
递归
分治
本质
函数自调用
一种通过递归解决子问题的策略
子问题结构
不一定是结构相同的问题
必须是规模更小的相同问题
合并结果
不一定合并
必须合并子问题的解
举例算法
斐波那契、阶乘、DFS
快排、归并、二分查找

应用场景

场景
常用策略
排序类算法
分治（快排、归并）
数组查找/最值
分治（二分）
图遍历/树递归
递归
数值问题（如斐波那契）
递归/记忆化搜索
最大子数组和
分治（分治法 O(nlogn) 解法）
 
上一篇
03-查找算法
下一篇
05-动态规划
Loading...