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

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：

gopl.io/ch5/findlinks1

// Findlinks1 prints the links in an HTML document read from standard input.
package main

import (
    "fmt"
    "os"

    "golang.org/x/net/html"
)

func main() {
    doc, err := html.Parse(os.Stdin)
    if err != nil {
        fmt.Fprintf(os.Stderr, "findlinks1: %v\n", err)
        os.Exit(1)
    }
    for _, link := range visit(nil, doc) {
        fmt.Println(link)
    }
}

visit函數遍歷HTML的節點樹，從每一個anchor元素的href屬性獲得link,將這些links存入字符串數組中，並返回這個字符串數組。

// visit appends to links each link found in n and returns the result.
func visit(links []string, n *html.Node) []string {
    if n.Type == html.ElementNode && n.Data == "a" {
        for _, a := range n.Attr {
            if a.Key == "href" {
                links = append(links, a.Val)
            }
        }
    }
    for c := n.FirstChild; c != nil; c = c.NextSibling {
        links = visit(links, c)
    }
    return links
}

為了遍歷結點n的所有後代結點，每次遇到n的孩子結點時，visit遞歸的調用自身。這些孩子結點存放在FirstChild鏈表中。

讓我們以Go的主頁（golang.org）作為目標，運行findlinks。我們以fetch（1.5章）的輸出作為findlinks的輸入。下面的輸出做了簡化處理。

$ go build gopl.io/ch1/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元素標籤，就將其入棧，並輸出。

gopl.io/ch5/outline

func main() {
    doc, err := html.Parse(os.Stdin)
    if err != nil {
        fmt.Fprintf(os.Stderr, "outline: %v\n", err)
        os.Exit(1)
    }
    outline(nil, doc)
}
func outline(stack []string, n *html.Node) {
    if n.Type == html.ElementNode {
        stack = append(stack, n.Data) // push tag
        fmt.Println(stack)
    }
    for c := n.FirstChild; c != nil; c = c.NextSibling {
        outline(stack, c)
    }
}

有一點值得注意：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。