递归是解决问题最常用的方法，比如，解决二叉树问题，最容易想到的就是递归算法，首先处理根结点，然后递归处理左右子树。递归有一个比较大的问题，就是时间复杂度。

下面用两个例子，来阐述递归问题解决思路，以及递归改为递推后，用空间置换时间，降低时间复杂度。

一、过河卒问题

1、递推算法

对于使用递归算法来解决问题，我们一般先推出一道数学公式，然后“照葫芦画瓢”

image

问题描述：卒从A到达B，不能通过马所控制的点，请问一共有多少种走法？（过河卒不能后退）

分析：卒从A到达棋盘中任意一点(i,j),共有f(i,j)中走法。

因此，我们可以得到递归算法代码如下：

int f(int i, int j){
  if(i*j==0){
    return 1;
  }
  if(Hc(i,j)){
    return 0;
  }else{
    return f(i-1,j) + f(i,j-1);
  }
}

其中，被马控制的点Hc(i,j)的代码如下：

bool Hc(int i, int j){
  if(Math.abs(i-4) + Math.abs(j-2) == 3){  //马所在的位置在(4,2)
    return true;
  }
  return false;
}

2、递推算法的优化

当我们上级调试的时候发现，递归算法的耗时是非常严重的，因为递归的过程中，不会记录中间结果，导致在计算f(i-1,j)和f(i,j-1)的过程中，会进行重复计算【中间有许多节点是重复的】

1）递推算法

将递归转为递推。递归是从结果推算，递推则是从开始忘结果推算，理解上可能困难了一点。
直接看代码：

int [][]G = new int [100][100]; //全局变量，自动初始化为全0
int f(int m, int n){
  for(int i=0;i<=m;i++){ //边界赋值为1
    G[i][0] = 1;
  }
  for(int j=0;j<=n;j++){ //边界赋值为1
    G[0][j] = 1;
  }
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n; j++){
      if(Hc(i,j)){
        G[i][j] = 0;
      }else{
        G[i][j] = G[i-1][j] + G[i][j-1];
      }
    }
  }
return G[m][n];
}

递推算法和递推算法的思想差不多，不过需要用额外的空间，记录中间结果，避免递推在跳入子函数中，对于已经计算过的值进行重新计算。

2）记忆搜索法

记忆搜索法用的也是递归的思想，不过通过额外的空间，将递归的每个阶段的计算结果保存下来。

int [][]MEM = new int [100][100]; //全局变量，自动初始化为全0
int f(int i, int j){
  if(i*j == 0){
    MEM[i][j] = 1;
    return 1;
  }
  if(Hc(i,j)){
    return 0;
  }
  if(MEM[i][j] != 0){
    return MEM[i][j];
  }else{
    MEM[i][j] = f(i-1,j) + f(i,j-1);
    return MEM[i][j];
  }
}

KEY: 通过建立“备忘录”，避免了重复计算，提高了算法的效率。

二、斐波那契数列

问题描述：满足的数列称为Fibonacci数列，现求任意给定n对应的

找公式：

1 递归算法

找到公式后，直接将公式改成算法即可：

int f(int n){
  if(n == 1 || n == 2){
    return 1;
  }else{
    return f(n-1) + f(n-2);
  }
}

简单明了，也很容易理解，但是跑起来比较慢，n=48时，完成一次运算耗时2min左右【不同机器和不同语言可能会不一样】，这种算法效率低下，但容易理解。

2、递推算法

int f(int n){
   int f1,f2,f2;
  if(n < 3){
    return 1;
  }
   f1 = f2 = 1;
   for(int i=3; i<= n; i++){
    f3 = f1+f2;
    f1 = f2;
    f2 = f3;
  }
  return f3;
}

3、记忆搜索法

int [] MEM= new int [1000];
int f(int n){
  if(n == 1 || n == 2){
    return 1;
  }
  if(MEM[n] != 0){
    return MEM[n];
  }else{
    MEM[n] = f(n-1) + f(n-2);
    return MEM[n];
  }
}