Golang 递归函数

在Golang中，递归函数是一个直接或间接调用自身的函数。这种技术通常用于解决需要重复计算或操作一个复杂问题的子问题的问题。

以下是一些Golang中递归函数的常见应用场景和相应的代码示例：

1. 计算阶乘：

package main
 
import "fmt"
 
func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}
 
func main() {
    num := 5
    fmt.Println("Factorial of", num, "is", factorial(num))
}

在这个例子中，factorial函数计算一个整数的阶乘。如果n为0，则返回1，否则返回n乘以n-1的阶乘。

2. 计算斐波那契数列：

package main
 
import "fmt"
 
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}
 
func main() {
    num := 10
    fmt.Println("Fibonacci of", num, "is", fibonacci(num))
}

在这个例子中，fibonacci函数计算斐波那契数列的第n项。如果n小于或等于1，则返回n，否则返回fibonacci(n-1)和fibonacci(n-2)的和。

3. 递归遍历目录：

package main
 
import (
    "fmt"
    "io/ioutil"
    "os"
)
 
func listFiles(dir string) {
    files, err := ioutil.ReadDir(dir)
    if err != nil {
        fmt.Println(err)
        return
    }
    for _, file := range files {
        path := dir + "/" + file.Name()
        if file.IsDir() {
            fmt.Println("directory:", path)
            listFiles(path)
        } else {
            fmt.Println("file:", path)
        }
    }
}
 
func main() {
    dir, err := os.Getwd()
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Println("Listing files in directory:", dir)
    listFiles(dir)
}

在这个例子中，listFiles函数递归遍历一个目录，打印出所有的文件和子目录。如果一个文件是目录，则继续遍历这个目录。

4. 二分查找：

package main
 
import "fmt"
 
func binarySearch(arr []int, l int, r int, x int) int {
    if r >= l {
        mid := l + (r-l)/2
        if arr[mid] == x {
            return mid
        }
        if arr[mid] > x {
            return binarySearch(arr, l, mid-1, x)
        }
        return binarySearch(arr, mid+1, r, x)
    }
    return -1
}
 
func main() {
    arr := []int{2, 3, 4, 10, 40}
    x := 10
    fmt.Println("Element is present at index:", binarySearch(arr, 0, len(arr)-1, x))
}

在这个例子中，binarySearch函数使用递归实现了二分查找算法。如果数组中含有x，则返回x在数组中的索引，否则返回-1。

以上示例展示了Golang中递归函数的一些常见用法