递推与递归的描述

递归和递推要求”原问题“与”问题边界“之间每个变换步骤具有相似性。

递推

若已知某处边界、小范围或特殊条件下，从这个边界为起点想原问题推导的方式就是递推。

递归

大多数时候，无法确定递推路线。采用递归：

  • 将问题规模缩小，划分为子问题。（自身调用自身）
  • 如果求解失败，使产生的影响失效，回到原位置。（回溯时还原现场）

递推和递归的应用

在使用枚举算法暴力遍历整个问题的”状态空间“时，经常需要递归。

按照规模大小，有如下几种方式：

枚举形式 状态空间规模 一般遍历方式
多项式 n^k^，k为常数 循环(for)、递推
指数 k^n^，k为常数 递归、位运算
排列 n! 递归、C++net_permutation
组合 $C_{n}^{m}$ 递归+剪枝

分治

分治法把一个问题划分为若干个规模更小的同类子问题，对子问题递归求解，然后回溯时推导出原问题的解。