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

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

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

数列

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

$a_0,a_1,a_2,...,a_{n-1},a_n$

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

一般要完整描述一个数列，方法有二：

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

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

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

递归过程(Recursive Process)

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

阶乘定义：
$f(n)=n!=n\times (n-1)\times \cdots \times 2\times 1$

等价于
$f(n)=\{\begin{array}{cc}1& n=0\\ nf(n-1)& n>0\end{array}$

$Fibonacci$函数定义：
$f(n)=\{\begin{array}{cc}0& n=0\\ 1& n=1\\ f(n-1)+f(n-2)& else\end{array}$

阶乘函数：

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)$。$Fibonacci$函数的时间和空间复杂度分别为$O({\varphi }^n)$和$O(n)$，其中$\varphi =(\sqrt{5}+1)/2$.

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

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

迭代过程(Iterative Process)

对于数列{ $a_n$}:
$a_0,a_1,a_2,...,a_{n-1},a_n$
假设已知其初始值$a_0$和递推公式$a_n=f(a_{n-1})$
我们可以迭代的求值

初始状态：$a_n=a_0$
状态更新：$a_n\leftarrow f(a_{n-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(1)$。$Fibonacci$函数的时间和空间复杂度分别为$O(n)$和$O(1)$.

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

小结

对于数列{ $a_n$}:
$a_0,a_1,a_2,...,a_{n-1},a_n$
假设已知其首项$a_0$和递推公式$a_n=f(a_{n-1})$

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

更多的例子

例一

$f(n)=\{\begin{array}{ccc}n& if& n<3\\ f(n-1)+2f(n-2)+3f(n-3)& if& n⩾3\end{array}$

首先，函数$f(n)$是自然数的函数（因为使用符号“$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)$（这个类似$Fibonacci$函数，值得仔细研究），空间复杂度$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(1)$.

例二

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

等价于

$f(b,n)=\{\begin{array}{ccc}1& if& n=0\\ bf(b,n-1)& if& n>0\end{array}$

递归计算

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

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

迭代计算

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

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

总结

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

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