C4
p---
theme: smartblue
highlight: arduino-light
---
# IV. 递归
## 1. 递归函数
您可能已经注意到，到目前为止我们还没有使用过 `for`、`while`或其它循环。事实上，函数式语言中并不存在这种结构。为了多次重复同一个操作，我们会使用**递归函数**。
递归函数的定义非常简单：这就是一个在给定时刻来调用自身的函数。一般来说，这类函数定义了两类情况（用`if`/`else`或者`match`）:一个不会递归的基层情况，以及一个会递归地调用函数到“上一级”的递归情况。
如果忘记编写基层情况的话，会和Python中`while(True)`有相同的效果：函数会无休止地调用下去，您的程序永远不会停止。
在OCaml中，需要在`let`之后使用关键词`rec`来表示这个函数是递归的。
举个例子，以下是一个递归地计算从0到 *n* 的和的函数：
```ocaml
(* 我们假定n不为复数即使int类型已经这样规定了 *)
let rec sum (n : int) : int =
if n = 0 then
0
else
n + (sum (n - 1))
```
在这个例子中：
- 基层情况为`0`，当n = 0时；
- 迭代情况为`n + (sum (n - 1))`；
为了理解在n = 3时怎样运行，我们可以观察一下图表：
或者另一种图表：
可以挑一个您喜欢的来看，重点是要理解这个函数是怎么进行计算的（如果您想的话，可以观察这两个图表）。一旦您知道了最主要的基础知识，您很容易就能理解所有的递归函数。
您需要的只是一次顿悟。如果您想要的话，这里还有一些递归函数的例子：
```ocaml
let rec factorial n =
if n < 2 then
1
else
n * (factorial (n - 1))
(* 如果你不知道什么是斐波那契数列的话:
https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0 *)
let rec fibonacci n =
if n < 2 then
1
else
(fibonacci (n - 1)) + (fibonacci (n - 2))
```
一个有助于理解递归数列概念的类比：为了计算 *u(n)*，我们总是需要 *u(n-1)*，所以我们需要计算所有的数值直到 *u(0)*,qui est défini de manière constante (le cas de base).
递归函数可以做到其它编程语言中循环的所有作用，甚至是更多。有些排序算法可以递归地实现，某些函数甚至无法用其他方式编写。在 OCaml（以及许多其他函数式语言）中，递归总是用于操作列表。
这是一个非常强大的工具，但你必须花时间来理解它。
## 2. 递归类型
递归类型和递归函数有些相似，是一种在定义中包含了自身的类型。因此这也属于加法类型，其中有一个（或数个）constructor与相同类型的数据关联。同样的，我们也会定义一个不递归的基层情况。
我们也可以构建一个元素列表：基层情况为一个空列表，递归情况为一个元素后再加另一个列表。
以下例子为一个整数列表：
```ocaml
type list_entier =
| Empty
| Element of int * list_entier
(* 列表[1,2,3]可以写做: *)
let my_list =
Element(
1,
Element(
2,
Element(
3,
Empty
)
)
)
```
但我们也可以假设一种更复杂的情况，比如说一个包含`int`或`float`的列表：
```ocaml
type list_numbers =
| Empty
| ElementEntier of int * list_numbers
| ElementReel of float * list_numbers
```
递归类型可以用递归函数遍历，递归函数可以对constructor使用`match`：
```ocaml
let sum_elements (list : list_entier) : int =
match list with
| Empty -> 0
| Element(x, rest) -> x + (sum_elements rest)
```
关于递归类型没有更多要说的了。理解它们的最好方法是去练习使用它们。
## 3. 课后练习
在经过两小节的学习后，这里有一份测验来检测自己。
已知我们定义了以下类型：
```ocaml
type itinerary =
| Arrive
| Take of string * itinerary
type recipe =
| Taste
| Cook of int * recipe (* int代表烹饪时长 *)
| Instruction of string * recipe
| TakeIngredient of string * recipe
```
完成以下递归函数：
```ocaml
(* 给出一种可阅读的路线。
*
* 比如：
*
* display(Take("rue of Mathematics", Take("road of Physique", Arrive)))
* = "Take the road of Mathematics, then take the road of Physique, then you have arrived."
*)
let rec display(i : itinerary) : string =
match i with
| Arrive -> "you have arrived."
| ______(name_road,continue) -> "take the " ^ name_road ^ ", then " ^ ______
```
<details>
<summary><答案点我></summary>
```ocaml
Take
```
</details>
<details>
<summary><答案点我></summary>
```ocaml
(display continue)
```
</details>
```ocaml
(* 记录菜谱的步骤数目 *)
let rec count_steps (r : recipe) : int =
match r with
| TakeIngredient(_, s) | Instruction(_, s) | Cook(_, s) -> ______
| Taste -> 0 (* 品尝不算在步骤内 *)
```
<details>
<summary><答案点我></summary>
```ocaml
1 + count_steps s 或 count_steps s + 1
```
</details>
```ocaml
(* 计算烹饪总时长，可能会有好几步 *)
let rec cook_total (r : recipe) : int =
match r with
| ______ -> 0
| Cook(time, s) -> ______
| Instruction(_, s) | TakeIngredient(_, s) -> cook_total s
```
<details>
<summary><答案点我></summary>
```ocaml
Taste
```
</details>
<details>
<summary><答案点我></summary>
```ocaml
time + (cook_total s) 或 (cook_total s) + time
```
</details>
我们想要编写一个递归类型来描述一个山洞，然后写出一个能找到出口的算法。我们有三种类型的“路”：
- 死胡同；
- 出口；
- 岔路口，有一条向左的路和一条向右的路。
完成下列加法类型的定义。
```ocaml
type cave =
| ______
| ______
| ______ of ______
(* 已知我们有这个函数： *)
let end_of_the_cave (c : cave) : bool =
match c with
| Impasse | Exit -> true
| ForkRoad(_, _) -> false
```
<details>
<summary><答案点我></summary>
```ocaml
Impasse
```
</details>
<details>
<summary><答案点我></summary>
```ocaml
Exit
```
</details>
<details>
<summary><答案点我></summary>
```ocaml
ForkRoad
```
</details>
<details>
<summary><答案点我></summary>
```ocaml
cave * cave
```
</details>