今天看看一些实战中用到递归的例子,第一个就是字符串全排列了,例如:

字符串'abc',那么全排列结果是:['abc','acb','bac','bca','cab','cba'],

字符串'abb',那么全排列结果是:['abb','bab','bba']。

这里我们可以假设f(str)代表str的全排列,那么f(abc)的全排列可以表示为[a+f(bc),b+f(ac),c+f(ab)],这样逐层展开,我们就可以求出一个字符串的全排列。

background Layer 1 f(abc) f(bc) f(ac) f(ab) a+ b+ c+ f(c) b+ f(b) c+ f(c) a+ f(a) c+ f(b) a+ f(a) b+ c b c a b a f(str)表示字符串str的全排列

那么我们可以写出代码:

上面代码还是比较难懂,其中Array.from(new Set())这种是数组去重的,因为全排列的时候会有一些重复的情况。上面的代码中有两层map和一个reduce,这个还是有点难理解的,我们看一个具体的过程:

background Layer 1 f(abc) f(bc) f(ac) f(ab) 递归得到 第一个map ['bc','cb'] 递归得到 ['ac','ca'] 递归得到 ['ab','ba'] a+ ['abc','acb'] b+ ['bac','bca'] c+ ['cab','cba'] 第二个map ['abc','acb','bac','bca','cab','cba'] reduce合并

斐波那契数列就是指f(n)=f(n-1)+f(n-2)的数列,其中f(0)=0,f(1)=1。计算f(n)的数值很容易让人产生一种错觉,让人很自然的觉得用递归的方法去做,例如如下结构:

background Layer 1 f(7) f(6) f(5) f(5) f(4) f(4) f(3) ... ... ... ... ... ... ... ...

其实这种是一种不正确的思路,因为这里面有大量重复的计算,而且是指数级别的,正确的做法就是从头开始遍历而不是从尾部开始递归。

青蛙跳台问题说的是有一个青蛙跳台阶,每次可以跳一格,也可以跳两格,问f(n)有多少种跳法。

首先f(1)=1,f(2)=2,现在假设要跳n台阶(n>2),那么青蛙可以选择先跳1格,剩下f(n-1)种跳法,或者先条2格,剩下f(n-2)种跳法,那么f(n)=f(n-1)+f(n-2)种跳法。这种其实就是上面的斐波那契数列了,解法相同,只不过初始值不同了。

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字