递推

递推的基本思想

• 递推法
  • 利用问题本身所具有的一种递推关系来求解问题的一种方法
• 递推
  • 是指从已知的初始条件出发，依据某种递推关系，逐次推出所要计算的中间结果和最终结果
    • 初始条件要么在问题本身中已经给定
    • 要么需要通过对问题的分析和化简来确定

递推的本质和特点

• 递推的本质
  • 把一个复杂的计算过程转化为一个简单过程的多次重复计算
• 可递推求解的问题的特点
  • 问题可以划分成多个状态
  • 除初始状态外，其他各状态都可用固定的递推关系来表示
• 递推的应用
  • 常用于按照一定的规律来计算序列中的指定项
  • 递推关系式通常不会直接给出

递推的方法

正向顺推

从已知条件出发，向着所求问题前进，最后与所求问题联系起来

方向逆推

• 从所求问题出发，向着已知条件靠拢，最后与已知条件联系起来
• 从问题的结果出发，一步一步还原出答案