分别以递归调用和迭代的方法求数列_迭代算法和递归算法

分别以递归调用和迭代的方法求数列_迭代算法和递归算法对于数列,递归和迭代的联系非常紧密。a0,a1,a2,…,an−1,ana_0,a_1,a_2,…,a_{n-1},a_na0​,a1​,a2​,…,an−1​,an​数列就是一串数字,数列来源于生活,有用的数列中蕴含着规则。要完整描述一个数列,方法有二:通项公式an=f(n)a_n=f(n)an​=f(n)递推公式其中通项公式是最一般的情况。由通项公式可以求得任意一…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

数列

对于数列,递归和迭代的联系非常紧密。

a 0 , a 1 , a 2 , . . . , a n − 1 , a n a_0,a_1,a_2,…,a_{n-1},a_n a0,a1,a2,...,an1,an

数列就是一串数字,数列来源于生活,有用的数列中蕴含着规则。

一般要完整描述一个数列,方法有二:

  • 通项公式 a n = f ( n ) a_n=f(n) an=f(n)
  • 递推公式

其中通项公式是最一般的情况。由通项公式可以求得任意一项。
递推公式给出了根据已有项的值求下一项的值的方法。通常递推公式包括一些边界值,因此根据递推公式也可逐项的求取整个数列。

因为数列大部分来源于生活实际,所以他们的形式往往是递推公式,为了更方便的计算数列的项,一个常见的任务是由递推公式求通项。但是有些数列无法由递推公式求出通项,比如阶乘数列{
n ! n! n!}和斐波那契数列{
F i b ( n ) Fib(n) Fib(n)}.

递归过程(Recursive Process)

由递推公式定义的数列,可以很自然地使用递归过程计算,就像直接把数学语言翻译为编程语言。

阶乘定义:
f ( n ) = n ! = n × ( n − 1 ) × ⋯ × 2 × 1 f(n)=n!=n\times(n-1)\times\cdots\times2\times1 f(n)=n!=n×(n1)××2×1

等价于
f ( n ) = { 1 n = 0 n f ( n − 1 ) n > 0 f(n)=\left\{\begin{matrix} 1&n=0\\ nf(n-1)&n>0 \end{matrix}\right. f(n)={
1nf(n1)n=0n>0

F i b o n a c c i Fibonacci Fibonacci函数定义:
f ( n ) = { 0 n = 0 1 n = 1 f ( n − 1 ) + f ( n − 2 ) e l s e f(n)=\left\{\begin{matrix} 0&n=0\\1&n=1\\f(n-1)+f(n-2)&else \end{matrix}\right. f(n)=01f(n1)+f(n2)n=0n=1else

阶乘函数:

def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n-1)

Fibonacci function

def fib(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fib(n-1) + fib(n-2)

用递归过程去实现这两个函数,简明又自然。但是缺点是复杂度高。对于阶乘函数,时间复杂度和空间复杂度都是 O ( n ) O(n) O(n) F i b o n a c c i Fibonacci Fibonacci函数的时间和空间复杂度分别为 O ( ϕ n ) O(\phi^n) O(ϕn) O ( n ) O(n) O(n),其中 ϕ = ( 5 + 1 ) / 2 \phi=(\sqrt5+1)/2 ϕ=(5
+
1)/2
.

显然,时间复杂度很高,这是递归的缺点。

仔细思考,我们会发现阶乘函数和 F i b o n a c c i Fibonacci Fibonacci函数都是关于自然数 n n n的函数,它们本质上构成了数列。但是我们在求值的时候没有把它们当做数列,仅仅利用递推公式递归得求值。如果我们根据递推公式,用参数更新的方式求第 n n n项,将是非常不同的思路。

迭代过程(Iterative Process)

对于数列{ a n a_n an}:
a 0 , a 1 , a 2 , . . . , a n − 1 , a n a_0,a_1,a_2,…,a_{n-1},a_n a0,a1,a2,...,an1,an
假设已知其初始值 a 0 a_0 a0和递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an1)
我们可以迭代的求值

初始状态: a n = a 0 a_n=a_0 an=a0
状态更新: a n ← f ( a n − 1 ) a_n\leftarrow f(a_{n-1}) anf(an1)

阶乘函数:

def factorial(n):
	a = 1
	for i in range(n):
		a = a*(i+1)
	return a

Fibonacci function

def fib(n):
	a, b = 0, 1
	for i in range(n):
		a, b = b, a+b
	return a

通过使用迭代过程实现这两个函数。对于阶乘函数,时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1) F i b o n a c c i Fibonacci Fibonacci函数的时间和空间复杂度分别为 O ( n ) O(n) O(n) O ( 1 ) O(1) O(1).

对于数列,一般存在递推公式的情况下,可以使用递归过程和迭代过程求解。这两者是想通的。

小结

对于数列{ a n a_n an}:
a 0 , a 1 , a 2 , . . . , a n − 1 , a n a_0,a_1,a_2,…,a_{n-1},a_n a0,a1,a2,...,an1,an
假设已知其首项 a 0 a_0 a0和递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an1)

递归过程中,首项 a 0 a_0 a0在称为边界值,递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an1)为递归式。
在迭代过程中,首项 a 0 a_0 a0称为状态初始值,递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an1)为状态更新方式。

更多的例子

例一

f ( n ) = { n i f n < 3 f ( n − 1 ) + 2 f ( n − 2 ) + 3 f ( n − 3 ) i f n ⩾ 3 f(n)=\left\{\begin{matrix} n&if&n<3\\f(n-1)+2f(n-2)+3f(n-3)&if&n\geqslant 3 \end{matrix}\right. f(n)={
nf(n1)+2f(n2)+3f(n3)ififn<3n3

首先,函数 f ( n ) f(n) f(n)是自然数的函数(因为使用符号“ n n n”作为自变量),那么就可以认为 f ( n ) f(n) f(n)是利用递推公式定义的数列的通项。因此可以使用递归过程和迭代过程实现。

迭代计算

def f(n):
	if n < 3:
		return n
	else:
		return f(n-1) + 2*f(n-2) + 3*f(n-3)

树形递归,时间复杂度约为 O ( 3 n ) O(3^n) O(3n)(这个类似 F i b o n a c c i Fibonacci Fibonacci函数,值得仔细研究),空间复杂度 O ( n ) O(n) O(n).

迭代计算

def f(n):
	a, b, c = 0, 1, 2
	for i in range(n):
		a, b, c = b, c, (c + 2*b + 3*c)
	return a

时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1).

例二

f ( b , n ) = b n f(b,n) = b^n f(b,n)=bn

等价于

f ( b , n ) = { 1 i f n = 0 b f ( b , n − 1 ) i f n > 0 f(b,n)=\left\{\begin{matrix} 1&if&n=0\\bf(b,n-1)&if&n>0 \end{matrix}\right. f(b,n)={
1bf(b,n1)ififn=0n>0

递归计算

def expt(b, n):
	if n == 0:
		return 1
	else:
		return b * expt(b, n-1)

线性递归,时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n).

迭代计算

def expt(b, n):
	a = 1
	for i in range(n):
		a *= b
	return a

时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1).

总结

可以发现对于一般的数列,如果存在递推公式,迭代过程比起递归过程是复杂度更低的方法。尤其是对于树形递归,时间复杂度由指数阶降为线性阶。而且迭代方法的空间复杂度总是 O ( 1 ) O(1) O(1).
迭代过程的核心思想是状态和状态更新。
首先应确定应设至几个状态变量,这取决于递推公式中 a n a_n an依赖几个前项。

递推公式 状态变量个数
f ( n ) = n f ( n − 1 ) f(n)=nf(n-1) f(n)=nf(n1) 1
f ( n ) = b f ( n − 1 ) f(n)=bf(n-1) f(n)=bf(n1) 1
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2) 2
f ( n ) = f ( n − 1 ) + 2 f ( n − 2 ) + 3 f ( n − 3 ) f(n)=f(n-1)+2f(n-2)+3f(n-3) f(n)=f(n1)+2f(n2)+3f(n3) 3

此外还要注意的是,在上表中,后3种情况都是利用一些前项的线性组合来求 a n a_n an,因此在迭代过程种无需关注循环变量 i i i,但是第一种情况在求 n ! n! n!时,需要利用 n n n来计算 a n a_n an,因此还要利用循环变量 i i i,这是需要仔细研究的。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/197447.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • opecv入门:3.6图片特效-浮雕效果[通俗易懂]

    opecv入门:3.6图片特效-浮雕效果[通俗易懂]importcv2importnumpyasnpimg=cv2.imread(‘image0.jpg’,1)imgInfo=img.shapeheight=imgInfo[0]width=imgInfo[1]gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)#newP=gray0-gray1+150相邻像素值相减为…

  • 仿淘宝实现多行星级评价

    仿淘宝实现多行星级评价

    2021年10月14日
  • 注意Mikrotik ROS Webproxy的“漏洞”

    注意Mikrotik ROS Webproxy的“漏洞”在使用ROSWebproxy做代理时,外网的IP也可以连入,将你的ROS代理服务器当作跳板!这种情况会引起外网网卡流量和内网网卡对不上的情况:如下图于是用Torch检查的时候发现了问题:1080口流量超大,而且在转发连表里没有流量,但是在WAN口的input连表里有高流量。也就是说和这个1080口连接的IP并没有和内网进行通!关闭代理后连接消失!…

  • 如何使用SpringBoot AOP 记录操作日志、异常日志?

    点击上方“全栈程序员社区”,星标公众号 重磅干货,第一时间送达 作者:咫尺的梦想_w cnblogs.com/wm-dv/p/11735828.html 平时我们在做项目时经常需要…

  • java 特点_JAVA的几个重要特点[通俗易懂]

    java 特点_JAVA的几个重要特点[通俗易懂]展开全部一.简单性:Java是纯62616964757a686964616fe58685e5aeb931333433663063面向对象语言,语法简单明了,易于掌握。Java使用接口取代了多重继承,并且取消了指针,因为多重继承和指针会使程序变得复杂。Java还会自动地收集内存垃圾,使得内存管理变得更为简单。Java还提供了丰富的类库、API文档以及第三方开发包,还有大量Java的开源项目。二.面向…

  • 素数算法总结

    素数算法总结素数算法总结转载自:_Wilbert在平时做题目或者进行预算的时候,素数的出现次数总是十分频繁。今天我们就来一点一点的说一说关于素数的一些算法。素数算法总结朴素判断素数算法Miller_Rabin素性测试筛选法容斥原理Meissel-Lehmer算法朴素判断素数算法就判断素数而言,事实上是非常简单的了。根据定义,判断一个整数n是否是素数,只需要去判断在整数区间[2,n-1]之内

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号