Swift) 재귀함수 이해하기

 

 

 

안녕하세요, 소들입니다 :)))

오늘은 재귀 함수에 대해 간단하게 알아볼 거예요!!!

 

재귀 함수는 잘 사용하면 코드가 매~우 간단해지기 때문에

한번 공부할 때 제대로 알아둡시당!!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 재귀 함수가 뭘까?

 

재귀 함수는 영어로 Recursive Call이라고 함..!

말 그대로 반복해서 호출하기 때문인데, 무엇을 반복하냐?

내 자신을 반복함

 

내 함수 안에서 내 함수를 호출하는 형태

 

자 다음과 같이 recersiveCall이란 함수 안에서 recersiveCall를 또 호출했잖음

 

 

func recersiveCall() {
    recersiveCall()
}

 

 

이 경우 recersiveCall이란 함수는 재귀 함수임!!

근데 지금은 이렇게 단순하게 한번 호출하고 끝났지만,

보통 재귀 함수는 내가 원하는 결과값을 얻기까지 재귀를 반복함!

 

이 재귀 함수는 알고리즘 작성 시 사용이 자주 되어, 익숙해져야 함 :)

예제로 익숙해져 보자..!!!

 

 

 

 

2. 재귀 함수 구현 해보기

 

자, 먼저 가장 대표적인 재귀함수의 예제인 factorial을 보겠음!

factorial이란 것은 

 

2! = 1 x 2

3! = 1 x 2 x 3

4! = 1 x 2 x 3 x 4

 

이런 것을 말하잖음!?

만약 num을 입력 받아서 num!을 반환하는 함수를

일반적으로 반복문을 사용해서 구현하려면 어케 하냐면,

 

 

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

 

 

이렇게 구현 할 것임!!!!!

 

근데 이 방법 말고, 재귀 함수를 이용해서 풀려면, 

먼저 factorial을 다음과 같이 단계적으로 접근하는 것이 필요함

 

1! = 1

2! = (1) x 2 = 1! x 2

3! = (1 x 2) x 3 = 2! x 3

4! = (1 x 2 x 3) x 4 = 3! x 4

 

이런 식으로! 따라서 

n!을 구하기 위해선 n * (n-1)!을 구하면 되는 것이고,

그렇다면 (n-1)! 을 구하기 위해선 (n-1) * (n-2)! 를 구하면 되는 것임

 

이런 식으로 마지막 factorial 실행이 1!이 될 때까지,

현재 값에서 -1 한 값을 다시 factorial로 반복 실행시켜주면 되는 것을 알 수 있음!!

 

흠.. 이론이 더 어려운 거 같네

재귀 함수로 직접 보면 더 이해하기 쉬움 :)

 

 

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

 

 

이렇게 짜면 됨!!!!

factorial이란 함수 내에서, factorial이란 함수를 또 부르는 것임. 

언제까지? 파라미터로 들어오는 num이 1이 될 때 까지!

 

왜냐? 만약 내가 4!를 구한다고 하면,

4!을 구한다는 것은, 4 * 3! 를 구하는 것이고,

3!를 구한다는 것은, 3 * 2! 를 구하는 것이고,

2!를 구한다는 것은, 2 * 1!를 구하는 것인데..!

1!은 1이지 0!을 구할 필요가 없잖음?

 

때문에 num이 1이 될 때까지, 계속해서 factorial 함수를 재귀 시키는 것임

따라서 위 factorial 재귀 함수의 탈출 조건은 "num이 1보다 작거나 같을 경우"가 되는 것임

 

참고로, 우리가 함수를 호출하는 것은 Stack처럼 관리가 되기 때문에,

재귀 함수도 당연히 Stack처럼 관리됨

따라서 우리가 4!라는 factorial을 얻기 위해 재귀 함수를 실행 시키면,

메모리 상으론 다음과 같이 저장되고 실행됨

 

 

 

 

 

자, 여기까지가 탈출 조건인 num이 1을 만나는 순간까지

factorial 함수가 4개나 스택에 쌓인 것임

 

그러면, num이 1이 되어서 더이상 factorial 함수가 재귀 호출되지 않고,

return을 때리면(빠져나오면) 어떻게 되냐면

 

 

 

 

이렇게 가장 마지막에 호출 됐던 factorial(1)부터 자신의 값을 반환하며,

맨 처음 호출됐던 factorial(4)까지, Stack에 쌓인 모든 factorial 함수가 return되는 것임

 

따라서 최종적으론 24란 값이 return 됩니다 :)

stack이기 때문에 LIFO 순서로 return! 이해가 가셨길 :))))))

 

 

 

 

3. 재귀 함수의 일반적인 형태

 

재귀 함수는 잘못 사용하면 조금 위험함

왜냐? 탈출 조건이 없으면 무한 재귀에 빠질 수 있기 때문임

 

 

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

 

 

만약 이렇게 num이 1일 때 탈출한다는 조건이 없으면

위 재귀 함수는 무한 재귀에 빠지게 되는 것임!!!

 

따라서, 보통 재귀 함수는 다음과 같이 생겨 먹음

 

 

func recursiveCall(입력) -> 출력 {
    if 입력 <= 일정 값 {                     // 탈출 조건 명시
        return 일정값 또는 입력값 또는 특정값
    }
    return recursiveCall(입력보다 작은 값)    
}

 

 

탈출 조건을 꼭 명시하며, 탈출 조건에 맞출 수 있는 입력을 구성해서 재귀를 호출함

보~통 이런 식으로 구성됨!

 

 

 

 

4. 재귀 함수(예제 factorial)의 시간 복잡도

 

자, 거의 마지막으로 위에서 살펴본 factorial 함수의 시간 복잡도에 대해 알아보겠음

재귀 함수는 사실 반복문으로 가능한 것을 좀 더 효과적으로? 표현하기 위해 사용되는 것임

고로, 재귀 함수가 가능하다 = 반복문으로도 가능하다란 말이고,

 

반복문과 형태만 다를 뿐

factorial(n)은 n-1번의 factorial() 함수를 호출해서 곱셈 함

이말인즉, 반복문을 n-1번 호출한 것과 동일하단 것임

때문에 O(n-1)이지만, 빅오 표기법 상 상수는 날려버리니

 

O(n)

 

이 된 것임

 

 

 

 

5. 재귀 함수의 공간 복잡도

 

공간 복잡도가 시간 복잡도에 비해선!!! 안 중요한 것은 맞지만, 이 정도는 짚고가도 좋을 듯!

우리가 위에서 factorial을 반복문과 재귀 함수 두 가지로 구현 했잖음?

 

근데 for 반복문의 경우

 

 

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

 

 

factorial 함수를 실행시켰을 때, 

result란 변수 1개, 루프 상수 n 1개로, 총 2개의 공간 복잡도가 생김

따라서 이는 빅오 표기법으로 O(1)에 해당함 (입력과 상관없이 상수니까)

 

근데 재귀 함수로 구현할 경우,

 

 

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

 

 

factorial은 함수이기 때문에, 재귀 호출될 때마다 stack에 저장됨

그말이 무엇이냐면, 함수가 10번 재귀 호출되면, 

파라미터 상수 num이 10개 생성되어 각각 메모리에 올라간단 말임

 

따라서 입력 n에 따라 (n-1)만큼 변수가 생성되니까

재귀 함수의 공간복잡도는 빅오 표기법으로 O(n)에 해당함

 

그래서 뭐 재귀 함수의 메모리 낭비를 줄이기 위해

꼬리 재귀 함수 이런 게 있다는데 이건 여기선 안다루겠음 :)

 

 

 

 

 

 

.

.

.

오늘은 재귀 함수 포스팅 끝 :)

근데 익숙해지기까진 여러 문제를 풀어봐야 할 것 같고...!!

언제 사용해야 효율적일지를 계속 생각해봐야 할듯 하다!!

피드백, 궁금증은 언제나 댓글 주세여~~ 20,000!