Golong 語言如何實現遞歸？

****說到遞歸函數這個東西，別看名字高大上，真要在 Golang（Go 語言）裏寫，其實一不小心就把自己繞暈了，****我當年第一次寫遞歸找文件目錄的時候，腦殼都轉麻了。但話說回來，只要你把幾個關鍵點弄清楚，其實寫起來挺爽的，甚至有點 “優雅”！

這篇就從我實戰經驗出發，帶你搞懂 “在 Golang 裏怎麼寫遞歸函數”，順帶踩幾個坑出來，保你一看就會、馬上能寫！

啥是遞歸？簡單說下

一句話：遞歸就是函數自己調自己！

比如你讓一個函數去算個階乘，5! = 5*4*3*2*1，用循環可以算，但也可以讓這個函數說：

“我要算 5 的階乘，那我先算 4 的階乘再乘 5”
然後它又去算 4 的階乘，說 “那我先算 3 的階乘乘 4”
一直遞推下去，直到 1 爲止

這種 “自我遞歸” 就叫遞歸函數。本質就是：大問題化小，小問題重複解決，最後合起來搞定。

用 Go 實戰一個：階乘計算

直接上代碼：

package main

import"fmt"

func factorial(n int) int {
if n == 0 {
return1// 遞歸終止條件
 }
return n * factorial(n-1) // 遞歸調用
}

func main() {
 result := factorial(5)
 fmt.Println("5 的階乘是：", result)
}

輸出：

5 的階乘是：120

是不是簡單暴力？兩行遞歸邏輯，乾淨利落！

遞歸必須有的關鍵點：一定要記住！

很多人一上來寫遞歸直接就進死循環了… 爲啥？因爲忘了下面這兩點：

終止條件必須寫！

沒終止條件就會無限遞歸，程序直接棧溢出（Stack Overflow）
比如上面階乘例子裏的：if n == 0 { return 1 }

遞歸一定要往終點靠近！

你不能原地打轉，要每次調用都 “向終點靠近一步”
比如每次都讓 n 減 1

再來個實際點的例子：遞歸列出文件夾下所有文件

這個我之前用在處理配置目錄自動分析中，貼段簡化版代碼：

package main

import (
"fmt"
"io/ioutil"
"os"
"path/filepath"
)

func listFiles(path string) {
 files, err := ioutil.ReadDir(path)
if err != nil {
  fmt.Println("讀取目錄失敗:", err)
return
 }

for _, file := range files {
  fullPath := filepath.Join(path, file.Name())
if file.IsDir() {
   listFiles(fullPath) // 遞歸調用
  } else {
   fmt.Println("文件:", fullPath)
  }
 }
}

func main() {
 dir := "./"// 當前目錄
 listFiles(dir)
}

這段代碼幹了啥？

讀取目錄裏的文件
如果是目錄，遞歸繼續深入
如果是文件，打印出來

我當時拿來分析項目結構，處理配置分層，真的爽！遞歸寫出來就像一個樹形爬蟲，效率直接爆了！

遞歸的幾個使用場景，我用過的

1）處理樹形結構數據

比如組織架構、評論樓層、文件系統，都是天生遞歸結構

2）算法題（比如 LeetCode）

二叉樹遍歷、DFS、揹包問題、全排列組合，遞歸就是核心

3）數據分析裏的多層歸類

我之前寫過一個日誌處理，嵌套層級特別多，遞歸一下子就解了

我踩過的坑，順帶告訴你避免

坑 1：遞歸太深導致爆棧

Go 默認棧空間不大（大概 2MB），你遞歸個上萬層就崩了！

我之前寫個 JSON 解嵌套字段，數據太深，結果程序直接 panic：

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

解決：要麼用循環改寫，要麼控制遞歸層數或數據結構的深度。

坑 2：忽略終止條件，或者判斷錯了

這個最常見，遞歸函數寫錯判斷，比如：

if n < 0 {
   return 1
}

結果你傳個 1，1 -> 0 -> -1 -> -2 -> ...，就一直遞歸…

一定要提前對參數加限制，不然就 GG。

坑 3：重複計算太多，性能爆炸

經典案例就是斐波那契數列：

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

你試試傳個 40，CPU 嗡嗡響！

這個時候要用 緩存（Memoization） 或者改寫成 動態規劃：

var cache = make(map[int]int)

func fib(n int) int {
if val, ok := cache[n]; ok {
return val
 }
if n <= 1 {
return n
 }
 cache[n] = fib(n-1) + fib(n-2)
return cache[n]
}

性能立馬飛昇！

對了，還有個事，尾遞歸優化 Go 不支持！

有些語言（比如 Scala、Haskell）可以自動把尾遞歸優化成循環，避免爆棧。

Go 不行！

你寫再完美的尾遞歸，它都不管，棧照樣加，所以大型遞歸儘量還是改成循環吧。

最後總結一下

遞歸函數在 Golang 裏：

寫法簡潔、邏輯清晰
但一定要小心爆棧、終止條件、重複計算
處理樹形結構、文件遍歷、算法題特別香

能掌握遞歸，你很多問題思路就會從 “線性” 升級到“層級”，很多原本看不清的邏輯結構瞬間豁然開朗！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/kF0wVtnp8c6VK-HpCTpwdQ

坑 1：遞歸太深導致爆棧

猜你喜歡