Go语言指南-6.6 递归函数

作者: Golang资深开发

6.6 递归函数

当一个函数在其函数体内调用自身,则称之为递归。最经典的例子便是计算斐波那契数列,即前两个数为1,从第三个数开始每个数均为前两个数之和。

数列如下所示:

   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

下面的程序可用于生成该数列(示例 6.13 [fibonacci.go] $eBook-examples-chapter_6-fibonacci.go

   package main

   import "fmt"

   func main() {
    result := 0
    for i := 0; i <= 10; i++ {
    result = fibonacci(i)
    fmt.Printf("fibonacci(%d) is: %d\n", i, result)
    }
   }

   func fibonacci(n int) (res int) {
    if n <= 1 {
    res = 1
    res = fibonacci(n-1) + fibonacci(n-2)
    }
    return
   }

输出:

   fibonacci(0) is: 1
   fibonacci(1) is: 1
   fibonacci(2) is: 2
   fibonacci(3) is: 3
   fibonacci(4) is: 5
   fibonacci(5) is: 8
   fibonacci(6) is: 13
   fibonacci(7) is: 21
   fibonacci(8) is: 34
   fibonacci(9) is: 55
   fibonacci(10) is: 89

许多问题都可以使用优雅的递归来解决,比如说著名的快速排序算法。

在使用递归函数时经常会遇到的一个重要问题就是栈溢出:一般出现在大量的递归调用导致的程序栈内存分配耗尽。这个问题可以通过一个名为懒惰求值的技术解决,在 Go 语言中,我们可以使用管道(channel)和 goroutine(详见第 14.8 节)来实现。练习 14.12 也会通过这个方案来优化斐波那契数列的生成问题。 Go 语言中也可以使用相互调用的递归函数:多个函数之间相互调用形成闭环。因为 Go 语言编译器的特殊性,这些函数的声明顺序可以是任意的。下面这个简单的例子展示了函数 odd 和 even 之间的相互调用(示例 6.14 [mut_recurs.go] $eBook-examples-chapter_6-mut_recurs.go

   package main

   import (
    "fmt"
   )

   func main() {
    fmt.Printf("%d is even: is %t\n", 16, even(16)) // 16 is even: is true
    fmt.Printf("%d is odd: is %t\n", 17, odd(17))
    // 17 is odd: is true
    fmt.Printf("%d is odd: is %t\n", 18, odd(18))
    // 18 is odd: is false
   }

   func even(nr int) bool {
    if nr == 0 {
    return true
    }
    return odd(RevSign(nr) - 1)
   }

   func odd(nr int) bool {
    if nr == 0 {
    return false
    }
    return even(RevSign(nr) - 1)
   }

   func RevSign(nr int) int {
    if nr < 0 {
    return -nr
    }
    return nr
   }

练习题 练习 6.4

重写本节中生成斐波那契数列的程序并返回两个命名返回值(详见第 6.2 节),即数列中的位置和对应的值,例如 5 与 4,89 与 10。 练习 6.5

使用递归函数从 10 打印到 1。 练习 6.6

实现一个输出前 30 个整数的阶乘的程序。 n! 的阶乘定义为:n! = n * (n-1)!, 0! = 1,因此它非常适合使用递归函数来实现。

然后,使用命名返回值来实现这个程序的第二个版本。

特别注意的是,使用 int 类型最多只能计算到 12 的阶乘,因为一般情况下 int 类型的大小为 32 位,继续计算会导致溢出错误。那么,如何才能解决这个问题呢?

最好的解决方案就是使用 big 包(详见第 9.4 节)。

链接

文章列表

更多推荐

更多
  • Go安全-二、Go 编程语言 Go 语言规范,The Go playground,Go之旅,关键词,评论,类型,Boolean,数字的,通用编号,具体数字,无符号整数,Signed integers,浮点数,其他数字类型,一串, 在深入研究使用 GO 进行安全
    Golang资深开发

  • Go安全-三、使用文件 File basics,创建空文件,截断文件,获取文件信息,重命名文件,删除文件,打开和关闭文件,检查文件是否存在,检查读写权限,更改权限、所有权和时间戳,硬链接和符号链接,读写,复制文件,Seeking positions in a
    Golang资深开发

  • Go安全-一、Go 安全简介 About Go,Go语言设计,The History of Go,收养与社区,关于Go的常见批评,Go工具链,Go吉祥物,学习Go,为什么要用Go?,为什么使用 Go 进行安全保护?,为什么不使用 Python 呢?,为什么不使用 J
    Golang资深开发

  • Go安全-零、前言 这本书是给谁的,这本书涵盖的内容,充分利用这本书,下载示例代码文件,使用的惯例,联系,评论, 本书涵盖了 Go 编程语言,并解释了如何将其应用于网络安全行业。所涵盖的主题对于红色和蓝色团队、希望编写安全代码的开发人员以及希望保护其
    Golang资深开发

  • Go安全-十、爬虫 爬虫基础,使用 strings 包在 HTTP 响应中查找字符串,使用正则表达式查找页面中的电子邮件地址,从 HTTP 响应中提取 HTTP 头,使用 HTTP 客户端设置 Cookie,在 web 服务器上查找未列出的文件,更改请求的
    Golang资深开发

  • Go安全-六、密码学 散列,散列小文件,散列大文件,安全地存储密码,加密,加密安全伪随机数生成器CSPRNG,Symmetric encryption,AES,非对称加密,生成公钥和私钥对,对邮件进行数字签名,验证签名,TLS,生成自签名证书,创建证书签名请
    Golang资深开发

  • Go安全-七、安全 Shell(SSH) 七、安全 ShellSSH使用 GoSSH 客户端,Authentication methods,使用密码进行身份验证,使用私钥进行身份验证,验证远程主机,通过 SSH 执行命令,启动交互式 shell, 安全外壳(S
    Golang资深开发

  • Go安全-八、暴力破解 Brute forcing HTTP basic authentication,强制使用 HTML 登录表单,强制 SSH,Brute forcing database login, 蛮力攻击,也称为穷举密钥攻击,是指您尝试输入的
    Golang资深开发

  • Go安全-十三、实现漏洞利用 交叉编译,创建绑定壳,创建反向绑定壳,创建 web shell,查找可写文件,更改文件时间戳,更改文件权限,更改文件所有权, 后利用是指渗透测试的一个阶段,其中一台机器已经被利用,代码执行可用。主要任务通常是保持持久性,以便您可以
    Golang资深开发

  • Go安全-十四、总结 重述您所学的主题关于 Go 用法的更多思考,我希望你能从这本书中得到什么,了解法律、道德和技术界限,从这里到哪里去,获得帮助和学习更多,重述您所学的主题到目前为止,在本书中,我们讨论了许多关于Go和信息安全的话题。所涵盖
    Golang资深开发

  • 近期文章

    更多
    文章目录

      推荐作者

      更多