자료 구조 - 순환 (Recursion)

C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리

---

 

순환(Recursion)이란 

어떤 알고리즘 또는 함수가 자기 자신을 호출하여 문제를 해결하는 기법
 

순환의 강점

 
순환은 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
 

순환의 약점

 
함수 호출을 하게 되므로 반복에 비해 수행시간 / 기억 공간의 사용면에서 떨어질 수 있다.
 

순환의 원리

 
주어진 문제를 더 작은 동일한 문제로 분해하여 해결하는 divide and conquer 기법
 

1) 정수의 팩토리얼

// 순환 호출로 구현
func factorial(n: Int) -> Int {
  if n <= 1 { return 1 }
  return n * factorial(n: n-1)
}

// 반복문으로 구현
func factorial(n: Int) -> Int {
    var result = 1
    var n = n
    while n != 1 {
        result *= n
        n -= 1
    }
    return result
}

 
반복문을 통한 구현과 순환을 통한 구현은 모두 시간복잡도 O(n)을 갖는다. 
하지만 순환 호출의 경우 여분의 기억 공간이 더 필요하고
함수 호출을 위해 함수 파라미터들을 스택에 저장하는 것과 같은 작업이 필요하다.
 
 

2) 거듭 제곱의 계산

// 순환 호출로 구현
func power(x: Double, n: Int) -> Double {
    if n == 0 {
        return 1
    } else if n % 2 == 0 {
        return power(x: x * x, n: n / 2)
    } else {
        return x * power(x: x * x, n: (n - 1) / 2)
    }
}

// 반복문으로 구현
func power(x: Double, n: Int) -> Double {
    var result: Double = 1
    for _ in 0..<n {
        result *= x
    }
    return result
}

 
거듭 제곱을 순환으로 구현한 알고리즘은 중학생 수준의 수학적 사고가 필요하다.
이는 문제의 크기가 항상 절반으로 줄어들며 O(logn)의 시간 복잡도를 갖는다. (반복문은 O(n))
 
코드 가독성이 떨어지고 여전히 함수 호출이라는 오버헤드가 있지만,
n의 숫자가 커질 수록 수행 시간에서 이점을 볼 것이다.
 

3) 피보나치 수열의 계산

 

// 순환 호출로 구현
func fib(n: Int) -> Int {
    if n == 0 { return 0 }
    if n == 1 { return 1 }
    return fib(n: n-1) + fib(n: n-2)
}

 
피보나치 수열은 순환 호출로 구현하였을 때 가독성이 좋지만, 성능 상으로 매우 비효율적이다. 단순히 fib(7) 을 계산하기 위해 fib 메서드가 41번 호출되어야 한다. n이 25이면 거의 25만 번의 호출을 해야 한다.
 
사실상 피보나치 수열을 순환 호출을 사용하여 계산하는 것은 불가능하다.
 

 
 

// 반복문으로 구현
func fib(n: Int) -> Int {
    if n < 2 { return n }
    
    var result = 1
    var tmp = 0
    var prev = 0
    
    for _ in 2...n {
        tmp = result
        result += prev
        prev = tmp
    }
    
    return result
}

 
 
반복 구조를 사용하면 O(n)의 시간 복잡도를 얻을 수 있다.
다만 변수도 많고 코드를 읽기가 어렵다.
 

꼬리 재귀

 
재귀 함수 호출할 때 n의 크기가 커지면 스택 오버플로우가 발생할 수 있다.
이러한 단점을 보완하기 위해 나온 개념이 꼬리 재귀 (Tail Recursion)이다.
 
이는 재귀 함수를 호출할 때 스택을 재사용하면서 메모리를 과도하게 사용하지 않도록 최적화하는 방법이다.
 
가독성이 한결 나아졌다.

// 꼬리 재귀를 사용하여 구현
struct Fibonacci {
    func fib(n: Int) -> Int {
        return fibByTailRecursion(n: n)
    }
    
    private func fibByTailRecursion(n: Int, oneAgo: Int = 1, twoAgo: Int = 0) -> Int {
        var oneAgo = oneAgo
        var twoAgo = twoAgo
        
        if n == 0 {
            return twoAgo
        }
        
        if n == 1 {
            return oneAgo
        }
        
        let current = oneAgo + twoAgo
        twoAgo = oneAgo
        oneAgo = current
        
        return fibByTailRecursion(n: n - 1, oneAgo: oneAgo, twoAgo: twoAgo)
    }
}