好用的算法技巧5. 与递归有关的一些优化

2019年6月10日10:22:15 发表评论 25 views

5. 与递归有关的一些优化

(1).对于可以递归的问题考虑状态保存

当我们使用递归来解决一个问题的时候,容易产生重复去算同一个子问题,这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题

问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?

这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法,则有

f(n) = f(n-1) + f(n - 2)。

递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码

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

不过对于可以使用递归解决的问题,我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归,是有很多重复计算的。如

好用的算法技巧5. 与递归有关的一些优化

就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存,当然用一个数组也是可以的,这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时,表示n还没计算过,当arr[n] != 0时,表示f(n)已经计算过,这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下:

//数组的大小根据具体情况来,由于int数组元素的的默认值是0
   //因此我们不用初始化
   int[] arr = new int[1000];
   public int f(int n) {
       if (n <= 2) {
           return n;
       } else {
           if (arr[n] != 0) {
               return arr[n];//已经计算过,直接返回
           } else {
               arr[n] = f(n-1) + f(n-2);
               return arr[n];
           }
       }
   }

这样,可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。

(2).考虑自底向上

对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。

不过,有时候当n比较大的时候,例如当 n = 10000时,那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。

对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道

f(1) = 1;

f(2) = 2;

那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来做。

代码如下:

public int f(int n) {
       if(n <= 2)
           return n;

       int f1 = 1;
       int f2 = 2;
       int sum = 0;

       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
   }

我们也把这种自底向上的做法称之为递推。

总结一下

当你在使用递归解决问题的时候,要考虑以下两个问题

(1). 是否有状态重复计算的,可不可以使用备忘录法来优化。

(2). 是否可以采取递推的方法来自底向上做,减少一味递归的开销。

作者:帅地
来源:知乎

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: