Go实战--go中函数递归(recursion)的使用(The way to go)

生命不止，继续 go go go !!!

什么是递归
Technically, a recursive function is a function that makes a call to itself. To prevent infinite recursion, you need an if-else statement (of some sort) where one branch makes a recursive call, and the other branch does not. The branch without a recursive call is usually the base case (base cases do not make recursive calls to the function).

有耐心的读读上面这段英文，然后默认你已经了解了什么是递归，那就开始实战之旅吧。

斐波那契数列(Fibonacci)

大概所有的语言学习递归的时候，都会写Fibonacci数列吧。

简单粗暴，直接上代码了：

package main

import "fmt"

func fib(n int) uint {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    n := 10
    fmt.Println(fib(n))
}

输出：55

通过闭包实现Fibonacci

go中允许使用函数闭包，我们之后会专门用一篇博客分享golang中的closure。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a := 0
    b := 1
    f := func() int {
        s := a
        a = b
        b = s + b

        return s
    }

    return f
}

func main() {
    f := fibonacci()
    for i := 0; i < 55; i++ {
        fmt.Println(f())
    }
}

通过递归打印html中的所有链接

下面的这个实战项目出自《The Go Programming Language》，可以翻阅。
其中源码的github地址：https://github.com/adonovan/gopl.io/

这里使用了golang.org/x/net/html包，自己去go get即可。从https://github.com/golang/net下载，然后把目录改成golang.org/x/net。

文档：
https://godoc.org/golang.org/x/net/html#example-Parse

下面就言归正传了：
递归visit函数：

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
}

从html文件中读取所有链接：

package main

import (
    "fmt"
    "io/ioutil"
    "os"
    "strings"

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

func main() {
    data, _ := ioutil.ReadFile("test.html")
    doc, err := html.Parse(strings.NewReader(string(data[:])))

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


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
}

通过管道读取某网址的所有链接：
想看一个Linux命令吧：

history | less

如果你懂这是什么意思，那我们就继续。

先通过fetch一个url:

package main

import (
    "fmt"
    "io/ioutil"
    "net/http"
    "os"
)

func main() {
    for _, url := range os.Args[1:] {
        resp, err := http.Get(url)
        if err != nil {
            fmt.Fprintf(os.Stderr, "fetch: %v\n", err)
            os.Exit(1)
        }
        b, err := ioutil.ReadAll(resp.Body)
        resp.Body.Close()
        if err != nil {
            fmt.Fprintf(os.Stderr, "fetch: reading %s: %v\n", url, err)
            os.Exit(1)
        }
        fmt.Printf("%s", b)
    }
}

验证一下：

然后重写上面的文件，把从文件读取改为从标准输入读取：

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)
    }
}

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
}

接下来就是通过管道执行了：

main.exe https://github.com/adonovan/gopl.io | D:\go_workspace\src\function_recursion\function_recursion.exe

可以看到输出结果：