面试题：Go性能优化之栈使用 - 高级难度

理解Go语言栈机制：
- Go语言使用动态栈，初始栈大小较小（例如2KB左右），随着需求增长会自动扩容。与传统静态栈（如C语言固定大小栈）不同，这在一定程度上降低了栈溢出风险。
优化递归调用：
- 尾递归优化：
  - 如果递归函数符合尾递归形式（即递归调用是函数的最后一个操作），可以通过改写函数实现类似循环的效果。例如：

// 传统递归
func factorial(n int) int {
    if n == 0 || n == 1 {
        return 1
    }
    return n * factorial(n - 1)
}

// 改写为尾递归形式（通过累加器）
func factorialTailRecursive(n, acc int) int {
    if n == 0 || n == 1 {
        return acc
    }
    return factorialTailRecursive(n - 1, n * acc)
}

手动模拟栈：
- 使用切片或链表手动模拟栈，将递归过程转换为迭代过程。比如对于二叉树的深度优先遍历，传统递归方式：

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func inorderTraversalRecursive(root *TreeNode) []int {
    var result []int
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        result = append(result, node.Val)
        inorder(node.Right)
    }
    inorder(root)
    return result
}

 - 手动模拟栈的迭代方式：

func inorderTraversalIterative(root *TreeNode) []int {
    var result []int
    var stack []*TreeNode
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)
        current = current.Right
    }
    return result
}

利用goroutine：
- 分散递归任务：
  - 对于深度递归调用，可以将递归任务分割成多个部分，利用goroutine并行处理。例如，在计算斐波那契数列时，对于较大的n，可以将计算F(n-1)和F(n-2)的任务放在不同的goroutine中：

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    var result int
    var ch1, ch2 = make(chan int), make(chan int)
    go func() {
        ch1 <- fibonacci(n - 1)
    }()
    go func() {
        ch2 <- fibonacci(n - 2)
    }()
    result = <-ch1 + <-ch2
    close(ch1)
    close(ch2)
    return result
}

控制并发数：
- 使用sync.WaitGroup和channel控制goroutine的并发数量，避免过多的goroutine同时运行导致资源耗尽。例如：

func worker(id int, jobs <-chan int, results chan<- int) {
    for j := range jobs {
        // 假设这里是递归计算任务
        result := fibonacci(j)
        results <- result
    }
}

func main() {
    const numJobs = 10
    jobs := make(chan int, numJobs)
    results := make(chan int, numJobs)
    var wg sync.WaitGroup
    const numWorkers = 3
    for w := 1; w <= numWorkers; w++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            worker(id, jobs, results)
        }(w)
    }
    for j := 1; j <= numJobs; j++ {
        jobs <- j
    }
    close(jobs)
    go func() {
        wg.Wait()
        close(results)
    }()
    for r := range results {
        fmt.Println("Result:", r)
    }
}

设置合理的栈大小限制：
- 在某些特殊情况下，可以通过runtime/debug包中的SetMaxStack函数设置栈大小的限制，但这需要谨慎使用，因为不合理的设置可能导致栈溢出或资源浪费。例如：

package main

import (
    "runtime/debug"
)

func main() {
    debug.SetMaxStack(1024 * 1024) // 设置最大栈大小为1MB
    // 程序逻辑
}

星途面试题库

面试题：Go性能优化之栈使用 - 高级难度

知识考点

面试题答案