文档章节

关于递归问题的探讨和优化,【线性递归】和【发散递归】

丌官尚雄
 丌官尚雄
发布于 07/12 21:53
字数 1806
阅读 71
收藏 2

递归介绍

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

递归分两个阶段,递和归

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

我们用数学表达式来看一下什么是递归的表示(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 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)

  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,也就是计算结果啦

线性递归

以上就是线性递归了,那什么是线性递归?

线性递归的意思就是 递归的次数递归参数 满足线性表达式关系

也就是递归函数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的时候,被乘矩阵为

看看 我们得出了什么,由一个发散递归变成了一个线性递归(斐波那契变成幂运算)

成功降维,我们只需要再把这个幂运算的递归形式变成整数快速幂就可以了

参照上面的证书快速幂,所以我们只需要把底数的参数由原来的整数换成矩阵就可以了。

总结

以上呢,就是快速幂了,无论是整数快速幂还是指数快速幂,都是为了简化运算减少遍历次数。使得算法复杂度陡然下降。

写在最后

如有错误请指正,如有想法可交流。

© 著作权归作者所有

丌官尚雄

丌官尚雄

粉丝 2
博文 35
码字总数 38328
作品 0
烟台
后端工程师
私信 提问
JavaScript尾递归优化探索

尾调优化 在知道尾递归之前,我们要直到什么是尾调用优化,因为尾调用优化是尾递归的基础。尾调用就是:在函数的最后一步调用另一个函数。 ps:最后一步必须是之久调用另一函数,而不能是一个...

a独家记忆
2018/07/18
0
0
了解递归的几种姿势 - 函数式编程

什么是递归 递归和迭代是一枚硬币的两面,在不可变的条件下,递归提供了一种更具表现力、强大且优秀的迭代替代方法 递归函数由以下两个主要部分组成: 基准 递归条件 递归主要的核心思想是将...

苏里
06/13
0
0
[原]关于线性递归与尾递归

作为读书笔记使用: 线性递归: 1 fac(0) -> 1 ; 2 fac(N) -> N*fac(N-1). 尾递归: 1 fac(0,Sum) -> 2 Sum; 3 fac(N,Sum) -> 4 fac(N-1,Sum*N). 尾递归定义: 函数最后一步调用自身,即最后......

长平狐
2012/11/14
157
0
MySQL8.0 - 新特性 - CTE(Common Table Expressions)

前言 CTE也就是common table expressions是sql标准里的语法,很多数据库都能够支持,MySQL也在8.0版本里加入了CTE功能,本文主要简单的介绍下该语法的用法,由于笔者对server层了解不深,本文...

zhaiwx_yinfeng
06/15
0
0
一文了解 Java 应用程序性能优化指南

  在《2018 最具就业前景的 7 大编程语言》一文中,通过分析了来自 Indeed 的 25 门编程语言、栈和框架的数据,我们盘点了18年最具就业前景的七大编程语言,其中,Java毫无悬念拔得头筹。 ...

CSDN
2018/01/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

php 遇到 No input file specified的解决方法

(一)IIS Noinput file specified 方法一:改PHP.ini中的doc_root行,打开ini文件注释掉此行,然后重启IIS 方法二: 请修改php.ini 找到 ; cgi.force_redirect = 1 去掉前面分号,把后面的1...

chenhongjiang
今天
5
0
MySQL 基础

一、常用命令 在命令行中,配置好环境变量后,通过cmd可以直接进入mysql命令行模式,同时列举几种常用命令 # 进入mysql数据库,密码可以先不写,打完-p后再输入,防止被别人看到mysql -u账...

华山猛男
今天
6
0
简单的博客系统(四)Django请求HTML页面视图信息--基于函数的视图

1. 编写用于查询数据的功能函数 应用目录 下的 views.py 文件通常用于保存响应各种请求的函数或类 from django.shortcuts import renderfrom .models import BlogArticles# Create your ...

ZeroBit
今天
5
0
用脚本将本地照片库批量导入到Day One中

因为目前iCloud 空间已经不足,其中95%都是照片,之前入手了DayOne,且空间没有限制,订阅费一年也不少,再加上DayOne作为一款日记App 也比较有名,功能方面最大的就是地理视图与照片视图,尤...

在山的那边
昨天
19
0
jupyter部署安装

python373 -m ipykernel install --name python373 ipython kernelspec list sc create myjupyterservice binpath="D:\apply\Python373\Scripts\jupyter-notebook --config=V:/my_work/jupyt......

mbzhong
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部