Swift) 재귀란?/재귀 함수/팩토리얼/꼬리 재귀

 

 

 

안녕하세요, UX를 고려하는 개발자 유자입니다.

오늘은 재귀 함수에 대해 알아보겠습니다!

 

 

 

 

 

1. 재귀 함수

 

재귀 함수란? 함수가 자기 자신을 호출하는 함수입니다.

 

 

func recursive() {
    recursive()
}

 

 

 

재귀함수는 자기 자신을 호출하기 때문에 무한 반복하는 함수를 만들기 쉽습니다.

 

 

재귀를 사용해서 만든 countdown 함수를 살펴보겠습니다.

 

 

func countdown(_ i:Int) {
    print(i)
    countdown(i-1)
}

 

 

countdown함수는 i를 출력한 뒤, 자기 자신을 호출합니다.

 

 

실제로 이렇게 코드를 작성하면

'함수 호출로 인해 무한 재귀가 발생한다’ 는 경고문이 뜹니다.

 

 

 

 

 

그리고 이 코드를 실제로 실행시키면 함수가 끝없이 실행됩니다.

(종료 단축키: command + .)

 

 

 

 

이와 같은 문제를 방지하기 위해

재귀 함수를 만들 때는 언제 재귀를 멈출지 알려줘야 합니다.

 

 

 

그래서 모든 재귀 함수는 다음 두 부분으로 나누어져 있습니다.

기본 단계(base case): 함수가 자기 자신을 호출하지 않는 경우(무한 반복으로 빠져들지 않게 하는 부분)
재귀 단계(recursive case): 함수가 자신을 호출하는 부분

 

 

 

 

 

countdown 함수에 기본 단계를 추가하면

 

 

func countdown(_ i:Int) {
    guard i >= 0 else { return }
    print(i)
    countdown(i-1)
}

countdown(3)

 

 

 

경고가 사라지고, 0까지만 출력되는 것을 확인할 수 있습니다.

 

 

 

 

 

 

 

 

 

2. 호출 스택

 

 

컴퓨터는 호출 스택이라는 스택을 사용합니다. 

스택은 나중에 들어온 프로세스가

가장 먼저 나가는 규칙을 따르는 자료구조입니다.

예시를 보겠습니다.

 

 

func greet(_ name:String) {
    print("Hello \(name)")
    greet2(name)
    print("Today is Monday")
    bye(name)
}

func greet2(_ name:String) {
    print("\(name)! How are you?")
}

func bye(_ name:String) {
    print("OK! Bye\(name)")
}

//함수 실행
greet("홍길동")

 

 

 

greet함수를 실행하면 가장 먼저

“Hello 홍길동”을 출력한 후, greet2 함수를 호출합니다.

greet2함수 실행되면 “홍길동! How are you?” 출력됩니다.

 

이제 greet2함수가 끝났으니,

다시 greet 함수로 돌아가 멈췄던 위치에서 실행을 계속합니다.

따라서 “Today is Monday”가 출력됩니다.

 

이 과정을 통해 함수의 실행이 완전히 끝나지 않아도 함수를 잠시 멈추고
다른 함수를 호출할 수 있다는 것을 알 수 있습니다.

 

지금까지 과정을 그림으로 표현하면 이런 모습입니다.

 

 

 

 

 

 

 

 

 

이제 bye 함수를 호출하여 “OK! Bye 홍길동”이 출력됩니다.

아직 greet 함수가 종료되지 않았기 때문에 다시 greet 함수로 돌아가지만,
더 이상 실행할 것이 없으므로 greet 함수도 종료됩니다.

 

 

 

 

 

 

 

 

재귀 함수는 이런 식으로 호출 스택을 사용합니다!

대표적인 재귀 함수인 팩토리얼 함수를 통해 이 과정을 확인해 보겠습니다.

 

 

 

 

 

 

 

 

 

3. 팩토리얼 함수

 

 

팩토리얼은 n!로 표현하며,

1부터 n까지의 모든 양의 정수를 곱한 값을 의미합니다.

예를 들어, 5!는 5*4*3*2*1로 정의됩니다.

 

 

이제 재귀를 사용해 팩토리얼을 계산하는 함수를 만든 뒤, 

호출하면 어떤 일이 일어나는지 살펴보겠습니다.

 

 

func factorial(_ num:Int) -> Int {
    if num == 1 {
        return 1
    } else {
        return num * factorial(num - 1)
    }
}

print(factorial(3))

 

 

 

처음에 입력된 3은 1이 아니므로 3 * factorial(2)를 반환합니다.

이제 factorial(2)를 호출합니다.

2 역시 1이 아니므로 2 *  factorial(1)을 반환합니다.

마지막으로 factorial(1)을 호출하면, 이 값은 1이므로 1이 반환됩니다.

 

 

 

 

 

 

 

 

 

 

4. 재귀 함수 메모리 문제

 

 

재귀 함수는 호출 스택을 사용하여

모든 중간 계산 결과를 저장해 메모리를 많이 소비할 수 있습니다.

 

 

재귀가 깊어지면 스택이 점점 쌓여 결국 가능한 메모리 한계를 초과해

비정상적으로 프로그램이 종료될 수 있습니다.

 

이 문제를 해결하기 위해 두 가지 방법을 알아보겠습니다.

 

 

 

 

4-1. 반복문

 

반복문을 사용하면 재귀 호출을 사용하지 않기 때문에

호출 스택을 사용하지 않습니다.

따라서 메모리 사용량을 줄일 수 있습니다.

다음은 반복문을 사용한 팩토리얼 함수입니다.

 

 

func factorial(_ num: Int) -> Int {
    var result = 1
    guard num > 1 else { return result }
    for n in 2...num {
        result *= n
    }
    return result
}

 

 

 

 

 

 

4-2. 꼬리 재귀

 

다음과 같이 자기 자신을 호출하는 함수가 있을 때

 

func tail(_ n: Int) -> Int {
    return tail(n - 1)
}

 

 

자신을 호출하는 부분이 함수의 마지막에 있는 경우를 꼬리 재귀라고 합니다.

 

 

 

 

반면, 아래와 같이

 

func nonTail(_ n: Int) -> Int {
    return n + nonTail(n - 1)
}

 

 

함수가 자기 자신을 호출한 뒤, n을 더하는 작업이 남아있을 경우 꼬리 재귀가 아닙니다.

 

 

 

꼬리 재귀를 사용하면 이론적으로는 메모리 사용량을 줄일 수 있습니다.

 

 

 

하지만 컴파일러가 꼬리 재귀 최적화를 지원하지 않는다면, 
꼬리 재귀를 사용해도 일반 재귀처럼 동작합니다.

 

 

 

Swift가 꼬리 재귀 최적화를 지원하는지 공식 문서를 살펴봤으나

명확한 언급이 없었습니다.

 

그래서 꼬리 재귀를 직접 실행해 확인해 보니,

 

 

 

 

 

 

스택 프레임이 계속 쌓이는 것을 볼 수 있었습니다.

 

 

 

realm문서에서는 최적화 옵션을 켜주면 컴파일러가 최적화할 수 있다고 나와 있지만

옵션이 달라 문서와 동일한 옵션을 설정해 실행해보진 못했습니다.

 

 

대신 설정 가능한 옵션을 모두 테스트해보았고 그 결과

모두 동일하게 스택 프레임이 쌓이는 것을 확인했습니다.

 

 

 

 

즉, Swift에서 꼬리 재귀 최적화가 항상 보장되지 않으므로,
안전성을 위해 꼬리 재귀보다는 반복문을 사용하는 것을 추천해 드립니다!

 

 

 

 

---

 

 

이렇게 재귀에 대해서 알아봤습니다.

재귀 함수는 복잡한 문제를 간결하게 해결할 수 있으며,

코드의 가독성을 높이는 장점이 있습니다!