• 56171

    文章

  • 559

    评论

  • 47

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

关于递归问题的探讨和优化,【线性递归】和【发散递归】(未完待续,更新中)

695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

欢迎来到梁钟霖个人博客网站。本个人博客网站提供最新的站长新闻,各种互联网资讯。 还提供个人博客模板,最新最全的java教程,java面试题。在此我将尽我最大所能将此个人博客网站做的最好! 谢谢大家,愿大家一起进步!

递归介绍

首先来说一下递归,我们不讲概念,我只说一下递归本身,有需要的同学请自行查阅资料。

递归分两个阶段,递和归

  • 递:是用来描述函数在何种情况下需要调用自身递下去
  • 归:是用来限定函数何时回归,因为程序不可能无限制的走下去

我们用数学表达式来看一下什么是递归的表示

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 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,浮点后面的数字会自动丢弃

现在我们模拟一下程序是如何跑的 power(2, 21)

  1. res = 1
  2. while循环,此时y = 21 = 10101(二进制)
  3. if(y&1),y = 10101(二进制),判断结果为true(二进制的最低位是1)
  4. res = res * x = 1 * 2 = 2
  5. x = x * x = 2 * 2 = 2^2
  6. y >>= 1 = 1010(二进制)
  7. while循环,此时y = 10101(二进制)
  8. if(y&1),y = 1010(二进制),判断结果为false(二进制的最低位是0)
  9. x = x * x = 2^2 * 2^2 = 2^4
  10. y >>= 1 = 101(二进制)
  11. while循环,此时y = 101(二进制)
  12. if(y&1),y = 101(二进制),判断结果为true(二进制的最低位是1)
  13. res = res * x = 2 * 2^4 = 2^5
  14. x = x * x = 2^4 * 2^4 = 2^8
  15. y >>= 1 = 10(二进制)
  16. while循环,此时y = 10(二进制)
  17. if(y&1),y = 10(二进制),判断结果为false(二进制的最低位是0)
  18. x = x * x = 2^8 * 2^8 = 2^16
  19. y >>= 1 = 1(二进制)
  20. while循环,此时y = 1(二进制)
  21. if(y&1),y = 1(二进制),判断结果为true(二进制的最低位是1)
  22. res = res * x = 2^16 * 2^5 = 2^5
  23. x = x * x = 2^16 * 2^16 = 2^32
  24. y >>= 1 = 0(二进制)
  25. while循环结束
  26. retrun res,也就是计算结果啦

未完待续


 转载至链接:https://my.oschina.net/tensai/blog/3073578。


转载原创文章请注明出处,转载至: 梁钟霖个人博客www.liangzl.com

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤
注册梁钟霖个人博客