很多编程语言都支持递归函数,Go语言也不例外,所谓递归函数指的是在函数内部调用函数自身的函数,从数学解题思路来说,递归就是把一个大问题拆分成多个小问题,再各个击破,在实际开发过程中,递归函数可以解决许多数学问题,如计算给定数字阶乘、产生斐波系列等。
构成递归需要具备以下条件:
注意:编写递归函数时,一定要有终止条件,否则就会无限调用下去,直到内存溢出。
下面通过几个示例来演示一下递归函数的使用。
下面我们就以递归函数的经典示例 —— 斐波那契数列为例,演示如何通过Go语言编写的递归函数来打印斐波那契数列。
数列的形式如下所示:
使用Go语言递归函数实现斐波那契数列的具体代码如下所示:
package main
import "fmt"
func main() {
result := 0
for i := 1; i <= 10; i++ {
result = fibonacci(i)
fmt.Printf("fibonacci(%d) is: %d\n", i, result)
}
}
func fibonacci(n int) (res int) {
if n <= 2 {
res = 1
} else {
res = fibonacci(n-1) + fibonacci(n-2)
}
return
}
输出结果为:
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且 0 的阶乘为 1,自然数 n 的阶乘写作n!,“基斯顿·卡曼”在 1808 年发明了n!这个运算符号。
例如,n!=1×2×3×…×n,阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。
使用递归函数计算给定数的阶乘,示例代码如下所示:
package main
import "fmt"
func Factorial(n uint64) (result uint64) {
if n > 0 {
result = n * Factorial(n-1)
return result
}
return 1
}
func main() {
var i int = 10
fmt.Printf("%d 的阶乘是 %d\n", i, Factorial(uint64(i)))
}
输出结果为:
Go语言中也可以使用相互调用的递归函数,多个函数之间相互调用形成闭环,因为Go语言编译器的特殊性,这些函数的声明顺序可以是任意的,下面这个简单的例子展示了函数 odd 和 even 之间的相互调用:
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
}
运行效果如下所示: