数据结构与算法——递归

发表于 更新于 分类于 阅读次数：

递归的理解：

在电影院中问前一排的人：“自己是第几排”，前一排的人做同样的事：问前一排“自己是第几排”，一直到第一排（递），然后从第一排向后一排排地把数字传回来（归）

递推公式：

1
f(n)=f(n-1)+1 其中，f(1)=1 //f(n)是自己所在的排数，f(n-1)是前一排的排数，f(1)=1是第一排的排数

代码：

1
2
3
4
int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归的优缺点：

  1. 优点：代码的表达力很强，写起来简洁

  2. 缺点：空间复杂度高、有堆栈溢出风险java.lang.StackOverflowError、存在重复计算、过多的函数调用会耗时较多等问题。

  3. 针对电影院这个递归的堆栈溢出问题可通过限制递归调用的最大深度的方式解决

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int depth = 0; // 递归的深度

    // 设定n>0
    int f(int n) {
      ++depth；
      if (depth > 1000) throw exception;
      
      if (n == 1) return 1;
      return f(n-1) + 1;
    }

递归的问题：

问题一：有n个台阶，每次可以跨1个台阶或者2个台阶的走，问走完n个台阶有多少种走法？
递推过程：

1
2
3
4
5
6
f(1) = 1; //n=1时，一步1个台阶走完
f(2) = 2; //n=2时，一步2个台阶走完
f(n) = f(n-1)+f(n-2) 
//假设第一步是1个台阶，剩下的n-1个台阶有f(n-1)种方法走完
//假设第一步是2个台阶，剩下的n-2个台阶有f(n-2)种方法走完
//加起来就是f(n-1)+f(n-2)，即n个台阶的走法f(n)=f(n-1)+f(n-2)

伪代码如下：

1
2
3
4
5
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

为了避免重复计算，可用散列表来保存已经求解过的f(k)，递归调用f(k)时先检查是否计算过了

1
2
3
4
5
6
7
8
9
10
11
12
13
public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  // hasSolvedList可理解成一个Map，key是n，value是f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
  
  int ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}

问题二：推荐注册返佣金，给定一个用户的ID，查找这个用户的“最终推荐人”
推荐关系的数据库关系（D -> C -> B -> A）：

actor_id referre_id
B A
C B
D C

解决方法：

1
2
3
4
5
long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

学自 王争——《数据结构与算法之美》