Riguz：Riguz移动页面Blog:递归和迭代至Recursion and iteration，不留重定向

2023-12-19T09:06:02Z

Riguz移动页面Blog:递归和迭代至Recursion and iteration，不留重定向

←上一版本		2023年12月19日 (二) 09:06的版本
（没有差异）

imported>Riguz：这是读《计算机程序的构造和解释》的笔记。

2021-02-26T00:00:00Z

这是读《计算机程序的构造和解释》的笔记。

新页面

这是读《计算机程序的构造和解释》的笔记。

= 递归和迭代=
== 计算裴波拉切数列==
裴波拉切数列是很简单的过程，其数学公式如下：

$$
Fib(n)=\left\{
\begin{array}{rcl}
0 & {n = 0}\\
1 & {n = 1}\\
Fib(n-1) + Fib(n-2) & {n > 1}\\
\end{array} \right.
$$

使用递归非常容易解决，就是直接将这个公式翻译成计算机语言即可：

<syntaxhighlight lang="scheme">
(define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2)))
)
)
)
</syntaxhighlight>
这个递归算法虽然实现很简单，但却有比较大的性能问题，出现了不必要的计算。例如计算Fib(5)，其计算过程如下：

[[File:Fib-tree.png|600px|Fib(5)]]

其中Fib(2)就计算了三次。那么，如何使用迭代来计算呢？迭代的思想在于给定若干变量的初始值，不断根据规则进行计算来改变这些变量，最后进行N次之后得到最终的结果。

$$
\begin{cases}
a = Fib(1) \\
b = Fib(0)
\end{cases}
\xrightarrow[\text{进行迭代}]{}
\begin{cases}
a = a + b \\
b = a
\end{cases}
\xrightarrow[\text{通过n次迭代变成}]{}
\begin{cases}
a = Fib(n+1)) \\
b = Fib(n)
\end{cases}
$$

这样实际上需要三个变量：

$$
\begin{cases}
F_{n} \\
F_{n+1} \\
Count
\end{cases}
\xrightarrow[\text{初始值}]{}
\begin{cases}
F_{n} &= Fib(0)\\
F_{n+1} &= Fib(1) \\
Count &= n
\end{cases}
\xrightarrow[\text{第一次迭代}]{}
\begin{cases}
F_{n} &= Fib(1)\\
F_{n+1} &= Fib(0) + Fib(1) \\
Count &= n - 1
\end{cases}\\
\xrightarrow[\text{第n次迭代}]{}
\begin{cases}
F_{n} &= Fib(n)\\
F_{n+1} &= Fib(n-1) + Fib(n) \\
Count &= 0
\end{cases}
$$

那么，翻译成代码就是：

<syntaxhighlight lang="scheme">
(define (fib n)
(fib_iter 1 0 n)
)

(define (fib_iter a b i)
(if (= i 0)
b
(fib_iter (+ a b) a (- i 1))
)
)

</syntaxhighlight>

Recursion and iteration - 版本历史

Riguz：​Riguz移动页面Blog:递归和迭代至Recursion and iteration，不留重定向

imported>Riguz：​这是读《计算机程序的构造和解释》的笔记。

Riguz：Riguz移动页面Blog:递归和迭代至Recursion and iteration，不留重定向

imported>Riguz：这是读《计算机程序的构造和解释》的笔记。