Go语言的递归算法

1. 说明

递归（Recursion）算法，指一种通过重复将问题分解为相同子问题而解决问题的方法，递归可以实现与循环类似的效果

需要使用递归的场景通常具备以下特征

原始问题可分解成子问题且子问题与原始问题一致 有明确的终止条件

递归的常见应用如下

递归数据求解（Fibonacci函数） 二叉树、广义表等明显具有递归特性的数据结构形式 适用于递归解法的典型问题（如Hanoi问题）

递归算法并不常用，在大多数编程语言中其运行效率较低，占用栈空间更大

在递归调用的每一层中都使用了栈存储，递归次数过多易造成栈溢出

例如对于Python语言而言，每进入一个函数调用，都会增加一层栈帧，栈大小不是无限的从而造成栈溢出

2. 例子

2.1. 求数N的阶乘

数据N的阶乘公式：$n!=n\times(n-1)\times(n-2)...\times1$

代码如下

Gocontent_copy

package main

import (
    "fmt"
    "time"
)

func Factorial(n int64) int64 {
    if n < 2 {
    	return int64(n)
    }
    return n * Factorial(n-1)
}

func main() {
    var n int64
    var number int64 = 1

    fmt.Printf("Input n value: ")
    fmt.Scan(&n)

    var start = time.Now()
    result = Factorial(n)
    var elapsed = time.Since(start)

    fmt.Printf("Factorial %v! result is %v\nTotal times is %v", number, result, elapsed)
}

输出如下

Bashcontent_copy

➜  go run main.go
Factorial 25! result is 7034535277573963776
Total times is 298ns

2.2. Fibonacci

Fibonacci即斐波那契数列，即一个特殊数列（0 1 1 2 3 5 8 ...），特征如下

前二个数字为0、1或1、1 从第三个数字开始的值是前两个数字之和

Go求解斐波那契数列函数如下

Gocontent_copy

package main

import (
    "fmt"
    "time"
)

func Fibonacci(n int) int {
    if n == 1 || n == 2 {
    	return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

func main() {
    var number int = 50

    var start = time.Now()
    var result int = Fibonacci(number)
    var elapsed = time.Since(start)

    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}

输出如下

Bashcontent_copy

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 40.354931919s

3. 效率对比

递归的缺点在开头就已经说过了，因为其重复调用会导致栈溢出，而且在大多数编程语言中递归的效率也不如普通循环

以Fibonacci函数为例，改写为循环

Gocontent_copy

package main

import (
    "fmt"
    "time"
)

func main() {
    var number int = 50

    var n1 int = 0
    var n2 int = 1
    var result int = 0

    var start = time.Now()
    for n := 2; n <= number; n++ {
    	result = n1 + n2
    	n1 = n2
    	n2 = result
    }

    var elapsed = time.Since(start)
    
    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)

}

输出如下

Bashcontent_copy

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 226ns

可以看到时间差距非常明显，这也是递归算法在实际应用中较为劣势的一点

4. 尾调用消除

前文提到，对于递归调用而言性能较差的原因是在递归调用的每一层中都使用了栈存储

过多的栈帧占用导致内存占用呈现一个波峰上升的趋势，对递归调用而言，优化其执行效率的思路就是减少其栈帧的产生

在函数编程语言中，语言标准通常会要求编译器或运行平台实现尾调用消除

尾调用 （tail call） 指的是一个函数的最后一条语句也是一个返回调用函数的语句(Wiki)，以Fibonacci为例写一个go语言的尾调用消除例子如下

Gocontent_copy

package main

import (
    "fmt"
    "time"
)

func Fibonacci(n int, n1 int, n2 int) int {
    if n == 0 {
    	return n1
    }
    return Fibonacci(n-1, n2, n1+n2)
}

func main() {
    var number int = 50

    var start = time.Now()
    var n1 int = 0
    var n2 int = 1
    var result int = Fibonacci(number, n1, n2)
    var elapsed = time.Since(start)

    fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}

Bashcontent_copy

➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 443ns

可以看到，执行效率几乎可以媲美循环写法