[알고리즘] 재귀 함수 with Swift

재귀란?

자기 자신으로 다시 돌아간다는 의미!

 

재귀는 문제를 더 작은 부분으로 나누고, 각 부분의 문제를 해결한 후 결과를 조합해 전체 문제의 답을 찾는 문제 해결 방법

반복 알고리즘으로 해결할 수 있는 문제는 모두 재귀 알고리즘으로도 해결할 수 있고, 재귀 알고리즘이 더 간결한 형태일 때가 많음

 

재귀 알고리즘은 자기 자신을 호출하는 함수나 메서드를 사용함

입력을 변경하고 자신을 호출하면서 그 결과를 전달하는 방식으로 작동함

따라서 재귀 함수가 자기 자신을 끝도 없이 호출하지 않도록 재귀 알고리즘을 빠져나가는 종료 조건이 반드시 필요!

 

재귀 함수는 자신을 호출할 때마다 알고리즘의 종료 조건에 가까워짐

결국 종료 조건을 만족해 문제가 해결되면 함수는 자신을 호출하는 일을 멈춤

 

재귀 알고리즘이 되려면?

1. 반드시 종료 조건이 있어야 한다.

2. 반드시 자기 자신의 상태를 변경하면서 종료 조건에 가까워져야 한다.

3. 반드시 자기 자신을 재귀적으로(다시 돌아와) 호출해야 한다.

 

팩토리얼을 예시로 반복/재귀 알고리즘을 구현해 보겠음

 

반복 알고리즘

func factorial(_ n: inout Int) -> Int {
    var result = 1
    while(n > 0) {
        result *= n
        n -= 1
    }
    return result
}

let n = 5
print(factorial(&n))    // 120

 

 

재귀 알고리즘

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial1(n-1)
}

print(factorial(5))    // 120

이 factorial 함수는 내부적으로 return 문을 만날 때 마다 그 반환값을 스택(Stack)에 담는 형태

스택은 데이터를 추가한 순서대로 데이터를 제거함!

 

 

재귀를 사용해야 할 때

재귀로 해결할 수 있는 문제는 반복으로도 해결할 수 있음

재귀의 장점은 간결함!

재귀의 단점은 내부 스택에 데이터를 저장하므로 메모리를 더 소비할 때가 많음

또한 알고리즘이 어떻게 작동되고 있는지 한눈에 파악하기 어려운 편이므로 반복 알고리즘에 비해 디버깅(오류 수정)이 어려울 수 있음

 

메모리 사용량이 중요하다면 반복 알고리즘을 선택하고, 그렇지 않다면 재귀 알고리즘의 간결함을 선택!