본문으로 건너뛰기

재귀 함수

재귀란?​

재귀(Recursion) 는 함수가 자기 자신을 호출하는 기법입니다. 복잡한 문제를 동일한 구조의 더 작은 문제로 분해할 수 있을 때 재귀가 자연스럽고 우아한 해법을 제공합니다.

재귀 함수는 반드시 두 가지 요소를 가져야 합니다.

  • 기저 조건(Base Case): 재귀를 멈추는 조건. 없으면 무한 재귀 → 스택 오버플로우 발생
  • 재귀 단계(Recursive Step): 문제를 더 작은 단위로 줄이고 자기 자신을 호출
package main

import "fmt"

// 카운트다운 — 가장 간단한 재귀 예제
func countdown(n int) {
    if n <= 0 {        // 기저 조건
        fmt.Println("발사!")
        return
    }
    fmt.Println(n)
    countdown(n - 1)   // 재귀 단계: n을 줄이면서 호출
}

// 리스트의 합 — 재귀적 접근
func sumList(nums []int) int {
    if len(nums) == 0 { // 기저 조건: 빈 슬라이스
        return 0
    }
    return nums[0] + sumList(nums[1:]) // 첫 원소 + 나머지의 합
}

func main() {
    countdown(5)
    fmt.Println()

    nums := []int{1, 2, 3, 4, 5}
    fmt.Println("합계:", sumList(nums))
}

실행 결과:

5
4
3
2
1
발사!

합계: 15

팩토리얼​

팩토리얼은 재귀의 교과서적인 예제입니다. n! = n × (n-1)! 이라는 정의 자체가 재귀입니다.

package main

import (
    "fmt"
    "math/big"
)

// 기본 팩토리얼 (int — 작은 수에만 사용)
func factorial(n int) int {
    if n <= 1 { // 0! = 1, 1! = 1
        return 1
    }
    return n * factorial(n-1)
}

// 큰 수 팩토리얼 — big.Int 사용
func factorialBig(n int) *big.Int {
    if n <= 1 {
        return big.NewInt(1)
    }
    result := factorialBig(n - 1)
    return result.Mul(result, big.NewInt(int64(n)))
}

// 반복문으로 구현한 팩토리얼 (비교용)
func factorialIter(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

func main() {
    // 재귀 vs 반복문 결과 비교
    for i := 0; i <= 10; i++ {
        rec := factorial(i)
        iter := factorialIter(i)
        match := "✓"
        if rec != iter {
            match = "✗"
        }
        fmt.Printf("%2d! = %7d %s\n", i, rec, match)
    }

    // 큰 수
    fmt.Println()
    fmt.Println("50! =", factorialBig(50))
    fmt.Println("100! =", factorialBig(100))
}

실행 결과:

 0! =       1 ✓
 1! =       1 ✓
 2! =       2 ✓
 3! =       6 ✓
 4! =      24 ✓
 5! =     120 ✓
 6! =     720 ✓
 7! =    5040 ✓
 8! =   40320 ✓
 9! =  362880 ✓
10! = 3628800 ✓

50! = 30414093201713378043612608166979581188299763898377856
100! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000

int는 64비트 시스템에서 최대 약 9.2 × 10¹⁸까지 표현합니다. 21! 부터는 오버플로우가 발생하므로 큰 수는 math/big 패키지를 사용하세요.

피보나치​

피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의됩니다. 재귀로 구현하기 쉽지만, 단순 재귀는 심각한 성능 문제가 있습니다.

package main

import (
    "fmt"
    "time"
)

// 단순 재귀 — O(2^n) — 매우 느림
func fibRecursive(n int) int {
    if n <= 1 {
        return n
    }
    return fibRecursive(n-1) + fibRecursive(n-2)
}

// 메모이제이션 재귀 — O(n) — 빠름
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    result := fibMemo(n-1, memo) + fibMemo(n-2, memo)
    memo[n] = result
    return result
}

// 반복문 — O(n) — 가장 빠름, 스택 오버플로우 없음
func fibIter(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    // 작은 수 비교
    fmt.Println("=== 피보나치 수열 (0~10) ===")
    for i := 0; i <= 10; i++ {
        fmt.Printf("F(%2d) = %d\n", i, fibIter(i))
    }

    fmt.Println()

    // 성능 비교
    n := 40

    start := time.Now()
    result := fibRecursive(n)
    elapsed1 := time.Since(start)
    fmt.Printf("단순 재귀   fib(%d) = %d (소요: %v)\n", n, result, elapsed1)

    start = time.Now()
    result = fibMemo(n, map[int]int{})
    elapsed2 := time.Since(start)
    fmt.Printf("메모이제이션 fib(%d) = %d (소요: %v)\n", n, result, elapsed2)

    start = time.Now()
    result = fibIter(n)
    elapsed3 := time.Since(start)
    fmt.Printf("반복문      fib(%d) = %d (소요: %v)\n", n, result, elapsed3)

    fmt.Printf("\n단순 재귀 vs 반복문: %.0f배 차이\n", float64(elapsed1)/float64(elapsed3+1))
}

실행 결과:

=== 피보나치 수열 (0~10) ===
F( 0) = 0
F( 1) = 1
F( 2) = 1
F( 3) = 2
F( 4) = 3
F( 5) = 5
F( 6) = 8
F( 7) = 13
F( 8) = 21
F( 9) = 34
F(10) = 55

단순 재귀   fib(40) = 102334155 (소요: ~500ms)
메모이제이션 fib(40) = 102334155 (소요: ~0s)
반복문      fib(40) = 102334155 (소요: ~0s)

단순 재귀로 fib(40)을 계산할 때 fib(2)가 약 5억 번 중복 계산됩니다. 메모이제이션은 한 번 계산한 값을 저장해 중복을 제거합니다.

꼬리 재귀 — Go의 한계​

꼬리 재귀(tail recursion) 는 재귀 호출이 함수의 마지막 동작인 형태입니다. 일부 언어(Haskell, Scala, Erlang 등)는 꼬리 재귀를 반복문으로 자동 변환하는 꼬리 재귀 최적화(TCO) 를 지원합니다.

Go는 꼬리 재귀 최적화를 지원하지 않습니다. 따라서 깊은 재귀는 스택 프레임을 계속 쌓아 결국 스택 오버플로우를 일으킵니다.

package main

import "fmt"

// 일반 재귀 팩토리얼 — 꼬리 재귀 아님
// n * factorial(n-1) — 재귀 호출 후 곱셈 연산이 남아있음
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1) // 재귀 호출이 마지막이 아님
}

// 꼬리 재귀 형태 팩토리얼 — accumulator 패턴
// 하지만 Go는 이를 최적화하지 않음!
func factorialTail(n, acc int) int {
    if n <= 1 {
        return acc
    }
    return factorialTail(n-1, n*acc) // 재귀 호출이 마지막 동작
}

// Go에서의 해법: 반복문으로 명시적 변환
func factorialLoop(n int) int {
    acc := 1
    for n > 1 {
        acc *= n
        n--
    }
    return acc
}

func main() {
    // 세 방법의 결과 비교
    for _, n := range []int{5, 10, 15, 20} {
        r1 := factorial(n)
        r2 := factorialTail(n, 1)
        r3 := factorialLoop(n)
        fmt.Printf("%2d! : 재귀=%d, 꼬리재귀=%d, 반복문=%d\n", n, r1, r2, r3)
    }

    // 깊은 재귀 — Go의 고루틴 스택은 동적으로 확장
    // 기본 goroutine 스택: 2KB에서 시작, 필요시 확장 (최대 1GB 기본값)
    fmt.Println("\nGo 고루틴 스택은 동적 확장 지원:")
    result := sumDeep(100000)
    fmt.Println("sumDeep(100000) =", result)
}

// 깊은 재귀 테스트
func sumDeep(n int) int {
    if n == 0 {
        return 0
    }
    return n + sumDeep(n-1)
}

실행 결과:

 5! : 재귀=120, 꼬리재귀=120, 반복문=120
10! : 재귀=3628800, 꼬리재귀=3628800, 반복문=3628800
15! : 재귀=1307674368000, 꼬리재귀=1307674368000, 반복문=1307674368000
20! : 재귀=2432902008176640000, 꼬리재귀=2432902008176640000, 반복문=2432902008176640000

Go 고루틴 스택은 동적 확장 지원:
sumDeep(100000) = 5000050000

Go의 고루틴 스택은 동적으로 확장 됩니다. 2KB에서 시작해 최대 1GB(기본값)까지 늘어납니다. 덕분에 수십만 번의 재귀도 가능하지만, 메모리를 많이 사용합니다. 수백만 번 이상의 깊은 재귀는 반복문으로 대체하세요.

트리 순회 재귀​

재귀가 반복문보다 훨씬 자연스러운 대표적인 사례는 트리 구조 순회 입니다.

package main

import "fmt"

// 이진 탐색 트리 노드
type TreeNode struct {
    Value       int
    Left, Right *TreeNode
}

// 노드 삽입
func (t *TreeNode) Insert(value int) *TreeNode {
    if t == nil {
        return &TreeNode{Value: value}
    }
    if value < t.Value {
        t.Left = t.Left.Insert(value)
    } else if value > t.Value {
        t.Right = t.Right.Insert(value)
    }
    return t
}

// 중위 순회 (inorder) — 정렬된 순서로 출력
func inorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    inorder(node.Left, result)
    *result = append(*result, node.Value)
    inorder(node.Right, result)
}

// 전위 순회 (preorder) — 루트 → 왼쪽 → 오른쪽
func preorder(node *TreeNode) []int {
    if node == nil {
        return nil
    }
    result := []int{node.Value}
    result = append(result, preorder(node.Left)...)
    result = append(result, preorder(node.Right)...)
    return result
}

// 트리 높이 계산
func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftH := height(node.Left)
    rightH := height(node.Right)
    if leftH > rightH {
        return leftH + 1
    }
    return rightH + 1
}

// 트리에서 값 검색
func search(node *TreeNode, value int) bool {
    if node == nil {
        return false
    }
    if value == node.Value {
        return true
    }
    if value < node.Value {
        return search(node.Left, value)
    }
    return search(node.Right, value)
}

// 트리의 모든 노드 합계
func sum(node *TreeNode) int {
    if node == nil {
        return 0
    }
    return node.Value + sum(node.Left) + sum(node.Right)
}

func main() {
    // 트리 구성
    var root *TreeNode
    values := []int{5, 3, 7, 1, 4, 6, 8, 2}
    for _, v := range values {
        root = root.Insert(v)
    }

    // 순회
    var sorted []int
    inorder(root, &sorted)
    fmt.Println("중위 순회 (정렬됨):", sorted)
    fmt.Println("전위 순회:", preorder(root))

    // 트리 속성
    fmt.Println("트리 높이:", height(root))
    fmt.Println("모든 값의 합:", sum(root))

    // 검색
    for _, v := range []int{4, 9, 1, 10} {
        fmt.Printf("  %d 존재: %v\n", v, search(root, v))
    }
}

실행 결과:

중위 순회 (정렬됨): [1 2 3 4 5 6 7 8]
전위 순회: [5 3 1 2 4 7 6 8]
트리 높이: 4
모든 값의 합: 36
  4 존재: true
  9 존재: false
  1 존재: true
  10 존재: false

실전 예제: 디렉터리 재귀 탐색​

파일 시스템은 재귀의 가장 실용적인 적용 사례입니다. 디렉터리 안에 또 다른 디렉터리가 있는 구조는 트리와 동일합니다.

package main

import (
    "fmt"
    "os"
    "path/filepath"
    "strings"
)

type FileInfo struct {
    Path  string
    Size  int64
    IsDir bool
    Depth int
}

// 디렉터리를 재귀적으로 탐색
func walkDir(dir string, depth int, result *[]FileInfo) error {
    entries, err := os.ReadDir(dir)
    if err != nil {
        return fmt.Errorf("디렉터리 읽기 실패 (%s): %w", dir, err)
    }

    for _, entry := range entries {
        fullPath := filepath.Join(dir, entry.Name())
        info, err := entry.Info()
        if err != nil {
            continue
        }

        *result = append(*result, FileInfo{
            Path:  fullPath,
            Size:  info.Size(),
            IsDir: entry.IsDir(),
            Depth: depth,
        })

        if entry.IsDir() {
            // 재귀 호출 — 서브 디렉터리 탐색
            if err := walkDir(fullPath, depth+1, result); err != nil {
                fmt.Println("경고:", err)
            }
        }
    }
    return nil
}

// 특정 확장자 파일 검색
func findFiles(dir, ext string) ([]string, error) {
    var found []string

    entries, err := os.ReadDir(dir)
    if err != nil {
        return nil, err
    }

    for _, entry := range entries {
        path := filepath.Join(dir, entry.Name())
        if entry.IsDir() {
            subFiles, err := findFiles(path, ext) // 재귀
            if err == nil {
                found = append(found, subFiles...)
            }
        } else if strings.HasSuffix(entry.Name(), ext) {
            found = append(found, path)
        }
    }
    return found, nil
}

// 디렉터리 총 크기 계산
func dirSize(path string) (int64, error) {
    var total int64

    entries, err := os.ReadDir(path)
    if err != nil {
        return 0, err
    }

    for _, entry := range entries {
        fullPath := filepath.Join(path, entry.Name())
        if entry.IsDir() {
            size, err := dirSize(fullPath) // 재귀
            if err == nil {
                total += size
            }
        } else {
            info, err := entry.Info()
            if err == nil {
                total += info.Size()
            }
        }
    }
    return total, nil
}

func main() {
    // 현재 디렉터리 탐색
    dir := "."

    var files []FileInfo
    if err := walkDir(dir, 0, &files); err != nil {
        fmt.Println("에러:", err)
        return
    }

    // 결과 요약
    var fileCount, dirCount int
    var totalSize int64
    for _, f := range files {
        if f.IsDir {
            dirCount++
        } else {
            fileCount++
            totalSize += f.Size
        }
    }

    fmt.Printf("탐색 결과:\n")
    fmt.Printf("  파일: %d개\n", fileCount)
    fmt.Printf("  디렉터리: %d개\n", dirCount)
    fmt.Printf("  총 크기: %d bytes\n", totalSize)

    // Go 파일 검색
    goFiles, err := findFiles(dir, ".go")
    if err == nil {
        fmt.Printf("  .go 파일: %d개\n", len(goFiles))
        for _, f := range goFiles {
            fmt.Printf("    %s\n", f)
        }
    }

    // filepath.WalkDir 사용 (표준 라이브러리 재귀 탐색)
    fmt.Println("\n표준 라이브러리 WalkDir 사용:")
    count := 0
    filepath.WalkDir(dir, func(path string, d os.DirEntry, err error) error {
        if err != nil {
            return nil
        }
        if !d.IsDir() && strings.HasSuffix(path, ".go") {
            count++
        }
        return nil
    })
    fmt.Printf("  .go 파일 수: %d\n", count)
}

실전 예제: JSON 재귀 파싱​

중첩된 JSON 구조는 재귀로 자연스럽게 처리할 수 있습니다.

package main

import (
    "encoding/json"
    "fmt"
    "strings"
)

// 중첩 JSON에서 모든 키-값 쌍을 평탄화
func flattenJSON(data any, prefix string, result map[string]any) {
    switch v := data.(type) {
    case map[string]any:
        for key, val := range v {
            newKey := key
            if prefix != "" {
                newKey = prefix + "." + key
            }
            flattenJSON(val, newKey, result) // 재귀
        }
    case []any:
        for i, item := range v {
            newKey := fmt.Sprintf("%s[%d]", prefix, i)
            flattenJSON(item, newKey, result) // 재귀
        }
    default:
        result[prefix] = v
    }
}

// JSON 깊이 계산
func jsonDepth(data any) int {
    switch v := data.(type) {
    case map[string]any:
        maxDepth := 0
        for _, val := range v {
            d := jsonDepth(val) // 재귀
            if d > maxDepth {
                maxDepth = d
            }
        }
        return maxDepth + 1
    case []any:
        maxDepth := 0
        for _, item := range v {
            d := jsonDepth(item) // 재귀
            if d > maxDepth {
                maxDepth = d
            }
        }
        return maxDepth + 1
    default:
        return 0
    }
}

func main() {
    rawJSON := `{
        "name": "Alice",
        "age": 30,
        "address": {
            "city": "서울",
            "zip": "04524",
            "geo": {
                "lat": 37.5665,
                "lng": 126.9780
            }
        },
        "hobbies": ["독서", "코딩", "등산"],
        "scores": [
            {"subject": "수학", "score": 95},
            {"subject": "영어", "score": 88}
        ]
    }`

    var data any
    if err := json.Unmarshal([]byte(rawJSON), &data); err != nil {
        fmt.Println("JSON 파싱 에러:", err)
        return
    }

    // 평탄화
    flat := map[string]any{}
    flattenJSON(data, "", flat)

    fmt.Println("=== 평탄화된 JSON ===")
    for k, v := range flat {
        fmt.Printf("  %-30s = %v\n", k, v)
    }

    fmt.Printf("\nJSON 깊이: %d\n", jsonDepth(data))

    // 특정 키 검색 (재귀)
    fmt.Println("\n'score'를 포함하는 키:")
    for k, v := range flat {
        if strings.Contains(k, "score") {
            fmt.Printf("  %s = %v\n", k, v)
        }
    }
}

실행 결과:

=== 평탄화된 JSON ===
  name                           = Alice
  age                            = 30
  address.city                   = 서울
  address.zip                    = 04524
  address.geo.lat                = 37.5665
  address.geo.lng                = 126.978
  hobbies[0]                     = 독서
  hobbies[1]                     = 코딩
  hobbies[2]                     = 등산
  scores[0].subject              = 수학
  scores[0].score                = 95
  scores[1].subject              = 영어
  scores[1].score                = 88

JSON 깊이: 4

재귀 vs 반복문 선택 기준​

기준재귀반복문
코드 가독성트리/그래프 등 자연스러운 재귀 구조에서 높음선형 처리에서 직관적
성능함수 호출 오버헤드, 스택 사용빠르고 메모리 효율적
스택 깊이깊으면 스택 오버플로우 위험제한 없음
상태 관리호출 스택이 상태를 자동 관리명시적 스택/상태 필요
최적화Go는 TCO 미지원컴파일러 최적화 유리

재귀를 선택할 때: 트리/그래프 순회, 분할 정복(병합 정렬, 퀵 정렬), 백트래킹, 파일 시스템 탐색, 재귀적으로 정의된 문제(피보나치, 팩토리얼)

반복문을 선택할 때: 깊이가 클 수 있는 경우, 성능이 중요한 경우, 꼬리 재귀를 직접 반복문으로 변환할 수 있는 경우

고수 팁​

스택 깊이 제어: 재귀가 필요하지만 깊이를 제한해야 할 때는 깊이 파라미터를 전달하세요. func process(node *Node, maxDepth int) 형태로 maxDepth가 0이 되면 중단합니다.

재귀를 스택으로 변환: 재귀를 명시적 스택([]T)으로 변환하면 스택 오버플로우 없이 동일한 로직을 구현할 수 있습니다. DFS(깊이 우선 탐색)를 반복문으로 구현할 때 이 기법을 사용합니다.

상호 재귀: 두 함수가 서로를 호출하는 상호 재귀도 Go에서 완전히 지원됩니다. 컴파일러가 전방 선언 없이 같은 패키지 내 함수를 참조할 수 있기 때문입니다.