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,...,an−1,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×(n−1)×⋯×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(n−1)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(n−1)+f(n−2)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,...,an−1,an
假设已知其初始值 a 0 a_0 a0和递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an−1)
我们可以迭代的求值
初始状态： a n = a 0 a_n=a_0 an=a0
状态更新： a n ← f ( a n − 1 ) a_n\leftarrow f(a_{n-1}) an←f(an−1)
阶乘函数：
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,...,an−1,an
假设已知其首项 a 0 a_0 a0和递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an−1)
递归过程中，首项 a 0 a_0 a0在称为边界值，递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an−1)为递归式。
在迭代过程中，首项 a 0 a_0 a0称为状态初始值，递推公式 a n = f ( a n − 1 ) a_n=f(a_{n-1}) an=f(an−1)为状态更新方式。
更多的例子
例一
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(n−1)+2f(n−2)+3f(n−3)ififn<3n⩾3
首先，函数 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,n−1)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(n−1) | 1 |
| f ( n ) = b f ( n − 1 ) f(n)=bf(n-1) f(n)=bf(n−1) | 1 |
| f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2) | 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(n−1)+2f(n−2)+3f(n−3) | 3 |
此外还要注意的是，在上表中，后3种情况都是利用一些前项的线性组合来求 a n a_n an，因此在迭代过程种无需关注循环变量 i i i,但是第一种情况在求 n ! n! n!时，需要利用 n n n来计算 a n a_n an，因此还要利用循环变量 i i i，这是需要仔细研究的。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/197447.html原文链接：https://javaforall.net
