递归

函数可以是递归的，这意味着函数可以直接或间接的调用自身。对许多问题而言，递归是一种强有力的技术，例如处理递归的数据结构。在4.4节，我们通过遍历二叉树来实现简单的插入排序，在本章节，我们再次使用它来处理 HTML 文件。

下文的示例代码使用了非标准包 golang.org/x/net/html ，解析 HTML 。golang.org/x/… 目录下存储了一些由 Go 团队设计、维护，对网络编程、国际化文件处理、移动平台、图像处理、加密解密、开发者工具提供支持的扩展包。未将这些扩展包加入到标准库原因有二，一是部分包仍在开发中，二是对大多数 Go 语言的开发者而言，扩展包提供的功能很少被使用。

例子中调用 golang.org/x/net/html 的部分 api 如下所示。 html.Parse 函数读入一组 bytes 解析后，返回 html.Node 类型的 HTML 页面树状结构根节点。HTML 拥有很多类型的结点如 text（文本）、commnets（注释）类型，在下面的例子中，我们只关注 < name key='value' > 形式的结点。

golang.org/x/net/html

package html

type Node struct {
    Type                    NodeType
    Data                    string
    Attr                    []Attribute
    FirstChild, NextSibling *Node
}

type NodeType int32

const (
    ErrorNode NodeType = iota
    TextNode
    DocumentNode
    ElementNode
    CommentNode
    DoctypeNode
)

type Attribute struct {
    Key, Val string
}

func Parse(r io.Reader) (*Node, error)

main 函数解析 HTML 标准输入，通过递归函数 visit 获得 links（链接），并打印出这些 links ：

ch5/findlinks1

Unresolved include directive in modules/ROOT/pages/ch5/ch5-02.adoc - include::example$/ch5/findlinks1/main.go[]

visit 函数遍历 HTML 的节点树，从每一个 anchor 元素的 href 属性获得 link ,将这些 links 存入字符串数组中，并返回这个字符串数组。

ch5/findlinks1

Unresolved include directive in modules/ROOT/pages/ch5/ch5-02.adoc - include::example$/ch5/findlinks1/main.go[]

为了遍历结点n的所有后代结点，每次遇到 n 的孩子结点时，visit 递归的调用自身。这些孩子结点存放在 FirstChild 链表中。

让我们以 Go 的主页（golang.org）作为目标，运行 findlinks 。我们以 fetch（1.5章）的输出作为 findlinks 的输入。下面的输出做了简化处理。

$ go build gopl.io/modules/fetch
$ go build gopl.io/ch5/findlinks1
$ ./fetch https://golang.org | ./findlinks1
#
/doc/
/pkg/
/help/
/blog/
http://play.golang.org/
//tour.golang.org/
https://golang.org/dl/
//blog.golang.org/
/LICENSE
/doc/tos.html
http://www.google.com/intl/en/policies/privacy/

注意在页面中出现的链接格式，在之后我们会介绍如何将这些链接，根据根路径（ https://golang.org ）生成可以直接访问的 url 。

在函数 outline 中，我们通过递归的方式遍历整个 HTML 结点树，并输出树的结构。在 outline 内部，每遇到一个 HTML 元素标签，就将其入栈，并输出。

ch5/outline

Unresolved include directive in modules/ROOT/pages/ch5/ch5-02.adoc - include::example$/ch5/outline/main.go[]

有一点值得注意：outline 有入栈操作，但没有相对应的出栈操作。当 outline 调用自身时，被调用者接收的是 stack 的拷贝。被调用者对 stack 的元素追加操作，修改的是 stack 的拷贝，其可能会修改 slice 底层的数组甚至是申请一块新的内存空间进行扩容；但这个过程并不会修改调用方的 stack 。因此当函数返回时，调用方的 stack 与其调用自身之前完全一致。

下面是 https://golang.org 页面的简要结构:

$ go build gopl.io/ch5/outline
$ ./fetch https://golang.org | ./outline
[html]
[html head]
[html head meta]
[html head title]
[html head link]
[html body]
[html body div]
[html body div]
[html body div div]
[html body div div form]
[html body div div form div]
[html body div div form div a]
...

正如你在上面实验中所见，大部分 HTML 页面只需几层递归就能被处理，但仍然有些页面需要深层次的递归。

大部分编程语言使用固定大小的函数调用栈，常见的大小从 64KB 到 2MB 不等。固定大小栈会限制递归的深度，当你用递归处理大量数据时，需要避免栈溢出；除此之外，还会导致安全性问题。与此相反，Go 语言使用可变栈，栈的大小按需增加（初始时很小）。这使得我们使用递归时不必考虑溢出和安全问题。

练习 5.1：修改 findlinks 代码中遍历 n.FirstChild 链表的部分，将循环调用 visit ，改成递归调用。

练习 5.2：编写函数，记录在 HTML 树中出现的同名元素的次数。

练习 5.3：编写函数输出所有 text 结点的内容。注意不要访问 <script> 和 <style> 元素，因为这些元素对浏览者是不可见的。

练习 5.4：扩展 visit 函数，使其能够处理其他类型的结点，如 images、scripts 和 style sheets 。