5.2. 递归

函数可以是递归的,这意味着函数可以直接或间接的调用自身。对许多问题而言,递归是一种强有力的技术,例如处理递归的数据结构。在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

  1. package html
  2. type Node struct {
  3. Type NodeType
  4. Data string
  5. Attr []Attribute
  6. FirstChild, NextSibling *Node
  7. }
  8. type NodeType int32
  9. const (
  10. ErrorNode NodeType = iota
  11. TextNode
  12. DocumentNode
  13. ElementNode
  14. CommentNode
  15. DoctypeNode
  16. )
  17. type Attribute struct {
  18. Key, Val string
  19. }
  20. func Parse(r io.Reader) (*Node, error)

main函数解析HTML标准输入,通过递归函数visit获得links(链接),并打印出这些links:

gopl.io/ch5/findlinks1

  1. // Findlinks1 prints the links in an HTML document read from standard input.
  2. package main
  3. import (
  4. "fmt"
  5. "os"
  6. "golang.org/x/net/html"
  7. )
  8. func main() {
  9. doc, err := html.Parse(os.Stdin)
  10. if err != nil {
  11. fmt.Fprintf(os.Stderr, "findlinks1: %v\n", err)
  12. os.Exit(1)
  13. }
  14. for _, link := range visit(nil, doc) {
  15. fmt.Println(link)
  16. }
  17. }

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

  1. // visit appends to links each link found in n and returns the result.
  2. func visit(links []string, n *html.Node) []string {
  3. if n.Type == html.ElementNode && n.Data == "a" {
  4. for _, a := range n.Attr {
  5. if a.Key == "href" {
  6. links = append(links, a.Val)
  7. }
  8. }
  9. }
  10. for c := n.FirstChild; c != nil; c = c.NextSibling {
  11. links = visit(links, c)
  12. }
  13. return links
  14. }

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

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

  1. $ go build gopl.io/ch1/fetch
  2. $ go build gopl.io/ch5/findlinks1
  3. $ ./fetch https://golang.org | ./findlinks1
  4. #
  5. /doc/
  6. /pkg/
  7. /help/
  8. /blog/
  9. http://play.golang.org/
  10. //tour.golang.org/
  11. https://golang.org/dl/
  12. //blog.golang.org/
  13. /LICENSE
  14. /doc/tos.html
  15. http://www.google.com/intl/en/policies/privacy/

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

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

gopl.io/ch5/outline

  1. func main() {
  2. doc, err := html.Parse(os.Stdin)
  3. if err != nil {
  4. fmt.Fprintf(os.Stderr, "outline: %v\n", err)
  5. os.Exit(1)
  6. }
  7. outline(nil, doc)
  8. }
  9. func outline(stack []string, n *html.Node) {
  10. if n.Type == html.ElementNode {
  11. stack = append(stack, n.Data) // push tag
  12. fmt.Println(stack)
  13. }
  14. for c := n.FirstChild; c != nil; c = c.NextSibling {
  15. outline(stack, c)
  16. }
  17. }

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

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

  1. $ go build gopl.io/ch5/outline
  2. $ ./fetch https://golang.org | ./outline
  3. [html]
  4. [html head]
  5. [html head meta]
  6. [html head title]
  7. [html head link]
  8. [html body]
  9. [html body div]
  10. [html body div]
  11. [html body div div]
  12. [html body div div form]
  13. [html body div div form div]
  14. [html body div div form div a]
  15. ...

正如你在上面实验中所见,大部分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。