如果问题的解和更小规模的解存在某种关系,就可以利用减治法自底向上或自顶向下地运用该关系。自顶向下求解使用递归算法,自底向上一般使用迭代实现。迭代实现往往优于递归实现。
减治法有三种主要变化形式:
减去一个常量。例如求解树的深度。
减去一个常量因子。例如二分查找。
减去的规模是可变的。例如辗转相除法。