递归问题的探讨和优化,【线性递归】和【发散递归】"/>
关于递归问题的探讨和优化,【线性递归】和【发散递归】
递归介绍
首先来说一下递归,我们不讲概念,我只说一下递归本身,有需要的同学请自行查阅资料。
递归分两个阶段,递和归
- 递:是用来描述方法在何种情况下需要调用自身递下去
- 归:是用来限定方法何时回归,因为程序不可能无限制的走下去
我们用数学表达式来看一下什么是递归的表示(x的y次幂)
f(x,y) = x * f(x, y - 1)
f(x, 1) = x
上面的结构就是递归的数学表示啦,第一个函数式是定义了函数如何递下去,第二个函数式定义了函数如何归回来。
递归的缺点
上面的例子其实是求x的y次幂,按照递归的思想,我们计算表达式的结果需要把x连乘y次,乍看起来没什么,但如果当y的次数足够大的时候,程序就可能会执行很慢,更甚至会发生爆栈的情况(也就是通常说的栈溢出)。
比如我们求2的21次幂的话,常规算法就是把2连乘21次,相应代码如下:
/*** @param x 底数* @param y 指数* @return x的y次幂*/
long power(int x, int y) {long res = 1;for(int i = 1; i <= b; i++) {res *= a;}return res;
}
是不是觉得有点low,那我们用递归的思想写一个方法
/*** @param x 底数* @param y 指数* @return x的y次幂*/
long power(int x, int y) {if(y == 1) {return x;} else {return x * power(x, y-1)}
}
上面两个方法都不好,因为复杂度还是O(n)
所以为了解决这个问题,我们引出一个概念:整数快速幂
整数快速幂
所谓快速幂,就是快速求幂次。
利用我们学过二进制,比如 21 ,它的二进制数字为 10101 ,也就是他可以分成21 = 16 + 0 + 4 + 0 + 1,也就是21 = 1 * 2^4 + 1 * 2^2 + 1 * 2^0。
那么我们计算2的21次幂就可以这么算了 我们这样分解2^21 = 2^16 * 2^4 * 2^1
如果要降低复杂度,首先应该是降低循环次数,再次就是降低重复计算的次数
先看代码
/*** @param x 底数* @param y 指数* @return x的y次幂*/
long power(int x, int y) {long res = 1;while(y) {if(y&1) {res = res * x; //如果二进制最低位为1,则乘上x^(2^i) }x = x * x; //将x平方 y >>= 1; //右移 相当于n/2}return res;
}
这里解释一下,y&1是进行的与运算,相当于判断y的二进制表示最低为是不是1,>>这个是右移运算符,就是把当前数的二进制表示向右移动一位,就是把10101变成1010.1,浮点后面的数字会自动丢弃,也就是10101右移一位变成了1010
现在我们模拟一下程序是如何跑的 power(2, 21)
- res = 1
- while循环,此时y = 21 = 10101(二进制)
- if(y&1),y = 10101(二进制),判断结果为true(二进制的最低位是1)
- res = res * x = 1 * 2 = 2
- x = x * x = 2 * 2 = 2^2
- y >>= 1 = 1010(二进制)
- while循环,此时y = 10101(二进制)
- if(y&1),y = 1010(二进制),判断结果为false(二进制的最低位是0)
- x = x * x = 2^2 * 2^2 = 2^4
- y >>= 1 = 101(二进制)
- while循环,此时y = 101(二进制)
- if(y&1),y = 101(二进制),判断结果为true(二进制的最低位是1)
- res = res * x = 2 * 2^4 = 2^5
- x = x * x = 2^4 * 2^4 = 2^8
- y >>= 1 = 10(二进制)
- while循环,此时y = 10(二进制)
- if(y&1),y = 10(二进制),判断结果为false(二进制的最低位是0)
- x = x * x = 2^8 * 2^8 = 2^16
- y >>= 1 = 1(二进制)
- while循环,此时y = 1(二进制)
- if(y&1),y = 1(二进制),判断结果为true(二进制的最低位是1)
- res = res * x = 2^16 * 2^5 = 2^5
- x = x * x = 2^16 * 2^16 = 2^32
- y >>= 1 = 0(二进制)
- while循环结束
- retrun res,也就是计算结果啦
线性递归
以上就是线性递归了,那什么是线性递归?
线性递归的意思就是 递归的次数 和 递归参数 满足线性表达式关系
也就是递归函数f(x) 需要递归的次数为 a*x+b 其中ab为常数
发散递归
所谓发散递归呢就是递归函数f(x)的递归次数是非线性的,例如x³-5x²-2x-8,这个函数式就是非线性的。 我们知道,当x的次数大于1的时候,在平面直角坐标系中会发生指数爆炸的情况。
根据上面我们说到的知识,也就意味着,发散递归会比线性递归更早的达到爆栈的临界点。
解决这一问题,就需要矩阵快速幂了。
矩阵
行列式和矩阵
要明白本文之后的内容,请大家回忆复习一下行列式和矩阵的基本概念和运算知识。
斐波那契数列(兔子)
x > 2: f(x) = f(x-1) + f(x-2)
x = 2: f(x) = 1
x = 1: f(x) = 1
同样的我们先用递归的算法来表示,如下:
int fei(int n) {if(n == 1||n == 2) {return 1;}return fei(n-1) + fei(n-2);
}
很简洁的代码,不在解释啦
至于这个递归执行了多少次,太具体的我也没算反正差不多是2的n次方吧
最简单算法就是,看结果是多少,就递归了多少次。
因为归回来的结果总是1,也就是好多个1相加,最后返回的计算结果。
斐波那契数列的方程组转化为矩阵计算的推导过程
已知:
- f(n) = f(n-1) + f(n-2) 得:
- f(n+1) = f(n) + f(n-1)
矩阵化表达如下
推导式
推导过程我就不写了,基本的矩阵运算。然后我们可得出下面的推导过程
那么当a=n-1的时候,被乘矩阵为
看看 我们得出了什么,由一个发散递归变成了一个线性递归(斐波那契变成幂运算)
成功降维,我们只需要再把这个幂运算的递归形式变成整数快速幂就可以了
参照上面的证书快速幂,所以我们只需要把底数的参数由原来的整数换成矩阵就可以了。
总结
以上呢,就是快速幂了,无论是整数快速幂还是指数快速幂,都是为了简化运算减少遍历次数。使得算法复杂度陡然下降。
写在最后
如有错误请指正,如有想法可交流。
转载于:
更多推荐
关于递归问题的探讨和优化,【线性递归】和【发散递归】
发布评论