[Swift Algorithm Note] 재귀함수 정리 (feat. Factorial)

대충은 알고 있었지만,, 지금까지는 알고리즘에 대한 정확한 개념 없이 문제를 해결해왔다.
하지만 점차 문제 수준이 높아지면서 알고리즘을 정확히 파악하고 있어햐 한다는 것을 느낌,,
따라서 오늘부터! 비교적 쉽고 필수적인 알고리즘부터 공부한 내용을 정리하려고 한다.
화이팅><

📎 재귀 함수(Recursive Call)

재귀 함수는 말 그대로,
함수에서 그 함수를 부르고, 또 부르고...!를 반복하는 것이다.

재귀 함수의 대표적인 예는 바로 팩토리얼이다.
팩토리얼 함수를 구현해봄으로써 재귀 함수를 이해해보자.

📌 팩토리얼 함수 구현

팩토리얼 계산의 진행 방식을 간단히 작성했다.

위와 같이 팩토리얼은 (요구한 숫자) * (그 전 숫자의 팩토리얼 값) 의 식으로 구성되고,
이를 간단히 표현하면 (num) * (num -1)! 이 되겠다.

여기서 알 수 있는 점은
3!을 구하려면 2!을 구해야 하고, 2!을 구하려면 1!를 구해야 하는 방식으로,
꼬리에 꼬리를 무는 풀이 방식이 필요하다는 것이다.
👉 팩토리얼을 포함하여, 이런 방식의 풀이가 필요할 때! 바로 재귀함수를 유용하게 사용할 수 있다.

위의 내용을 코드로 확인해보자.

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

print(Factorial(3)) // 6
print(Factorial(5)) // 120

먼저 Factorial 함수의 return 문을 보면, 위에서 구한 num * (num - 1)! 을 표현한 것을 확인 가능하다.
입력한 num 값에 대해 num - 1에 해당하는 Factorial 함수를 호출하고, num 값을 곱해 리턴한다.
전체적인 로직을 살펴보면, if 문에 작성한 예외처리에 도달할 때까지 함수 호출을 반복하다가
num이 2보다 작아지면 return num 구문을 시작으로, 쌓아놓은 계산을 진행하게 되는 방식이다.

몇 줄 되지 않는 간단한 함수지만,
막상 구현하려고 하면 복잡하게 느껴지는게 바로 이 재귀함수인듯 하다.ㅜ
말로 적은 설명이 조금 어려우니,, 대표로 Factorial(3)의 처리 과정을 그림으로 확인해보자.

메모리에 함수가 저장되는 과정을 순서대로 표현했다.
우선 3을 입력했기에 Factorial(2)를 호출하고, Factorial(2)는 또 Factorial(1)을 호출한다.
이 때 1은 2보다 작으므로 if문이 실행되어 1을 반환하게 되고, 본격적인 팩토리얼 계산이 시작된다.

이렇게 LIFO 순서대로 (stack 구조이기 때문)
마지막 return 값으로 이전에 호출된 함수의 계산 결과를 반환하고,
또 그 결과 값으로 그 이전 호출된 함수의 계산 결과를 반환하는 방식으로 진행되는 것이다.
따라서 최종 return 값으로 6이 반환됨을 확인할 수 있다.

---

📎 재귀 함수의 기본 형태

위에서 팩토리얼 함수를 구현해보며 재귀함수에 꼭 필요한 필수 요소들이 있음을 알 수 있었다.
재귀함수의 필수 요소들을 체크해보고, 기본 형태를 정리해보자.

📌 재귀함수의 필수 요소

• 함수 탈출 조건
• 함수 호출
• 리턴 값

무한 반복에 빠지지 않도록 하기 위해 탈출 조건을 정확히 명시해주고,
재귀 함수의 핵심인 함수 스스로를 호출하는 구문을 잘 작성해준다면 재귀함수의 기본 형태는 완성된다.

func recursiveCall(_ num: Int) -> /*반환 타입*/ {
    if /*탈출 조건*/ { return /*반복되는 함수 호출의 종료이자, 첫 번째 반환 값*/ }
    return return recursiveCall(/*새로운 입력 값*/)
}

위에서 작성한 필수 조건을 기반으로 재귀 함수의 기본 형태를 작성했다.
다양한 재귀 함수들이 존재하겠지만, 가장 기본적인 케이스를 표현했다.

---

👀 정리

팩토리얼 함수의 구현을 통해 재귀 함수를 이해하고, 사용 방법을 공부했다.

재귀 함수는 한마디로 'LIFO 반복 함수'라고 표현하고싶다.

개념은 어렵지 않지만, 막상 구현하려고 하면 머리 속에서 버퍼링이 걸린다,,
정확히 익혔으니, 무조건 연습을 많이 해보는 것이 중요할 것 같다.

💥 추가!!

재귀 함수는 장점도 명확하지만, 단점 또한 명확히 존재한다.

따라서 이 단점을 극복하기 위한 '꼬리 재귀 함수'에 대한 글을 다음에 다뤄보려고 한다.