우연히 어제 코딩테스트 관련 블로그를 보다가

"재귀적으로 문제를 해결 할 수 있다."

라는 문구를 봤다.

그런데 오늘 자료구조 특강 시간에 재귀함수의 대한 내용이 나와서 어?

이건 공부하라는 계시구나 ㅎㅎ 하고 공부해봤다.

재귀함수, 재귀호출 이런 말을 들을 때 잘 몰랐지만 내용을 배우면서 나도 모르게 재귀 호출을 사용한 방식으로 코테를 풀기도 했었더라.

그래서 오늘은 재귀의 대해 공부해봤다.

---

재귀적이다?

재귀적이다 라는 말은 프로그래밍에서 함수가 자기 자신을 호출하는 방식을 뜻한다고 한다.

재귀함수란

재귀함수는 자기 자신을 호출하는 함수를 인데,

일반적인 함수는 다른 함수나 연산을 호출하지만,

재귀함수는 자신의 이름을 다시 호출하여 작업을 수행한다.

재귀 호출이란

재귀 호출은 함수가 자기 자신을 호출하는 행동을 의미한다.

예로 어떤 함수 A가 내부에서 다시 함수 A를 호출한다면 이는 재귀 호출이다.

이런 호출 방식은 주로 문제를 작게 나누어 반복적으로 해결할 때 사용된다.

---

재귀 호출의 방식이 문제를 작게 나눠 반복적으로 해결할 때 사용되는거라면,

반복문과 비슷하다는건데, 어떤 차이 있을까?

재귀호출 VS 반복문

특징	반복문	재귀
동작 방식	반복 구조를 사용하여 조건에 따라 명령을 반복 실행	함수가 자기 자신을 호출하며 조건에 따라 종료
사용 방식	for, while 등의 키워드 사용	함수 내에서 자기 자신을 호출
가독성	간단한 반복 작업에는 더 직관적	복잡한 로직을 더 간결하게 표현 가능
메모리 사용	스택 메모리를 추가로 사용하지 않음	호출 스택 사용(함수 호출마다 스택 프레임 추가)
성능	반복문이 일반적으로 더 빠르고 효율적	재귀는 깊이가 깊을수록 성능이 저하될 가능성 있음
종료 조건	루프 조건 (i < 10 등)	재귀 호출 종료 조건 (ex: if count == 0)
적용 가능 문제	반복 작업, 고정된 반복 횟수	분할 정복, 백트래킹, 계층적 문제 (예: 트리 탐색)
코드 길이	단순 반복에서는 코드가 더 짧고 단순	조건부나 계층적 작업에서 코드가 더 간결
스택 오버플로우 위험	없음	재귀 깊이가 깊으면 스택 오버플로우 발생 가능

이렇게 표로 보니 보기가 쉽다.

재귀호출이 유용한 경우가 언제인지를 알아봤는데,
.
.
.

문제가 자연스럽게 작은문제로 나뉘는 경우나 트리와 같은 계층적 구조를 처리할 때,

그리고 분할 정복 알고리즘이 유용한 경우라고 한다.

---

1. 문제가 자연스럽게 작은 문제로 나뉘는 경우는

예로 피보나치 수열이나 팩토리얼계산, 이진탐색이 있다.

사실 이 중에서 아는게 없었어서 간략하게 어떤건지 알아놔야 "아 이럴때 재귀함수가 쓰이겠구나" 라고 알 수 있을 것 같아 정리했다.

1. 피보나치 수열
   피보나치 수열은 각 숫자가 앞의 두 숫자의 합으로 정의되는 수열이라고 한다.

• 기본적으로 시작 숫자는 0과 1이다. (예시 - 0, 1, 1, 2, 3, 5, 8,....)
• 쉽게 그냥 뒤에 숫자와 합한 숫자가 앞에 온다고 생각하면 될 것 같다.

2. 팩토리얼 계산
   팩토리얼은 어떤 숫자 n에 대해 1 부터 n까지의 모든 정수를 곱한 값이라고 한다.

• 팩토리얼 기호 라는 것도 있다 기호는 n! 이다.
• 예외적으로 0! = 1로 정의 된다고 한다. (예시 - 5! = 5 x 4 x 3 x 2 x 1 = 120)

3. 이진 탐색 (Binary Search)
   이진탐색은 정렬된 데이터에서 효율적으로 값을 찾는 알고리듬 이라고 하는데,
   데이터를 절반씩 나눠서 탐색하고 목표 값을 빠르게 찾아간다고 한다.

• 시간 복잡도가 O(log n)으로 매우 효율적인 장점이 있다.

알고리즘 동작
1. 배열의 중간값을 선택한다.
2. 중간값이 목표값보다 크면 왼쪽 절반만 탐색한다.
3. 중간값이 목표값보다 작으면 오른쪽 절반만 탐색한다.
4. 목표값을 찾거나, 탐색 범위가 없을 때까지 반복한다
예시)
배열 [1, 3, 5, 7, 9]에서 7을 찾는 과정이라 한다면,
중간값: 5 → 목표값 7보다 작다 → 바로 오른쪽 탐색 진행
오른쪽 배열 [7, 9] 에서 중간값 7 → 값 발견!!!!

이렇게 자연스럽게 작은 문제로 나뉘는 경우가 있다.

마지막 이진탐색의 경우 알고리듬 문제에서도 자주 보이는 패턴이다.

이렇게 여러 계산법을 공부하니 재밌다.

---

2. 트리와 같은 계층적 구조를 처리할 경우는

예로 파일 시스템은 디렉터리와 파일의 계층적 구조로 이루어진 것을 알 수 있다.

root/
├── folder1/
│   ├── file1.txt
│   └── file2.txt
├── folder2/
│   └── file3.txt
└── file4.txt

이렇게 사용하는 이유는 특정 디렉터리를 탐색하거나 하위 디렉터리를 순회할 때 트리구조가 적합하기 때문이라고 한다.

쉽게 말해 파일 시스템에서 재귀적 처리란

디렉터리(폴더) 안에 들어있는 항목(파일이나 다른 디렉터리)을 하나씩 살펴보고

그 안에 또 다란 디렉터리가 있다면 다시 같은 과정을 반복하는걸 의미하는 걸로 이해하면 될 것 같다.

이와 비슷하게 회사 조직도도 트리형태로 나타낼 수 있다.

CEO
├── 과장
│   ├── 팀장
│   ├── 사원
└── 부과장
    ├── 대리
    └── 사원

특정 직원의 상사나 하위 직원을 탐색하거나 전체 저직도를 출력할 때 사용된다.

이렇게 과정에서 디렉터리를 열어 내용물을 하나씩 검사하고,

디렉터리를 만나면 재귀적으로 다시 들어가서 탐색하는 것이 재귀적 처리의 핵심이라고 볼 수 있다.

---

3. 분할 정복 알고리듬이 유용한 경우

분할 정복 알고리짐은 문제를 작은 하위 문제로 나눠서 해결하고,

그 해결 방법을 결합해서 최종 답을 구하는 알고리즘 방식이다.

이 방식은 특히 규모가 큰 문제를 해결할 때 유용하다고 한다.

큰 문제를 작은 문제로 나눌 수 있을 때

아까도 말했다시피 분할 정복은 큰 문제를 여러개의 작은 문제로 나누어 해결하는 방법인데,

이런 방식은 문제 자체가 하위문제로 나누어질 수 있는 성질을 가질 때 유용하다.

예를 들면 퀵 정렬이나 머지 정렬은 배열을 반으로 나눠 각 부분을 정렬해준 후

다시 합쳐서 전체 배열을 정렬하는 방식인데,

이처럼 큰 문제를 작은 문제로 나누는 접근 방식이 필요한 문제에서 효과적이라는 것이다.

중복 계산을 피할 수 있을 때

분할 정복 알고리즘은 중복 계산을 피하기 위해 문제를 분할한 후,

각 하위 문제를 한번만 계산하고 그 결과를 결합해 최종 답을 도출하게 한다.

그렇게 하면 불필요한 중복 계산을 피할 수 있는데

예를 들어 피보나치 수열을 계산하게 된다면 일반적인 재귀 방법은 많은 중복 호출을 발생시킨다.

이걸 동적 계획법과 결합한 분할 정복 방식으로 계산을 피할 수 있다.

• 동적 계획법이란.. 복잡한 문제를 해결하기 위해서 작은 하위문제로 나눈 뒤
  각 하위문제의 결과를 저장해서 재사용함으로써 계산량을 줄이는 알고리즘 설계 기법이라고 한다.

배열이나 리스트를 정렬할 때

정렬 문제에서는 분할 정복이 가장 자주 사용된다고 할 수 있다.

배열을 분할해서 작은 배열들을 각각 정렬해주고 합치는 방식이 우리가 코테에서 자주 해왔던 방식이었다!

분할 정복 알고리즘의 특징

• 재귀적 접근 : 문제를 하위 문제로 나누고, 그 하위 문제들을 재귀적으로 풀어서 답을 구한다.
• 문제를 나누고, 결합하는 방식 : 각 하위 문제를 풀고, 그 결과를 합쳐서 전체 문제의 답을 구한다.
• 최적화 가능 : 많은 경우, 분할 정복을 통해 최적화된 해결 방법을 찾을 수 있다.
• 성능이 우수한 경우가 많다 : 큰 문제일수록 성능이 좋다. 예를 들어, 퀵 정렬이나 병합 정렬은 매우 큰 배열에서도 잘 작동한다.

---

재귀 사용 시 주의사항

1. 종료 조건을 정확히 설정해야 한다.

• 종료 조건이 없으면 스택 오버플로우 발생.

2. 재귀 깊이가 너무 깊으면 성능 저하.

• 반복문으로 대체하거나 꼬리 재귀(최적화)를 활용.

코드가 간결하고 문제의 계층적 구조를 그대로 표현할 수 있다보니 가독성에선 좋지만,

잘못 작성하면 무한 재귀에 빠질 위험이 있다고 한다.

---

더 이해하기 쉽게 간단한 예시로 비교를 해보자

1부터 N까지 합 계산한다고 가정했을 때

재귀)

func sum(_ n: Int) -> Int {
    if n == 0 { return 0 } // 종료 조건
    return n + sum(n - 1) // 자기 자신 호출
}
print(sum(10)) // 55

반복문)

func sum(_ n: Int) -> Int {
    var total = 0
    for i in 1...n {
        total += i
    }
    return total
}
print(sum(10)) // 55

코드로 보면 재귀는 직관적이고 간결하지만 스택에 각 상태를 저장해야해서 큰 값에서는 효율이 떨어질 수 있다.

그에 비해 반복문의 경우는 함수 호출 없이 반복만 수행하기 때문에 속도와 메모리에서 유리하다.

만약 문제를 풀면서 속도와 메모리가 중요한 상황이라면 반복문이 적합할 것이고,

문제를 계층적으로 이해하고 간결한 코드를 작성한다면 재귀가 적합할 것 같다.

사실 어떤걸 사용할 지는 문제의 성격이나 성능 요구사항에 따라 선택할 수 밖에 없을 것 같기도.

---

음 ...

오늘 재귀호출이 무엇인지를 좀 알게 된 시간이었다.

자기자신을 호출하는 함수...

그리고 어떤 작업을 계층적으로 처리하거나 반복적으로 해결하는데 유용하다는 것도 알게 되었다.

특히 종료 조건이 중요하다는게 좀 인상 깊었는데,

종료 조건이 없으면 마치 while 문처럼 무한 루프에 빠져 스택 오버플로우를 유발할 수 있다는 것도 흥미로웠다.

그리고 반복문과 비교하면서 두 가지의 접근 방식에 있어 장점과 단점도 살펴볼 수 있어서 좋았다.

• 재귀는 코드를 간결하게 작성할 수 있어 가독성이 좋았지만, 함수 호출로 인해 메모리를 추가로 사용한다는 단점이 있었다.

• 반복문은 명시적으로 상태를 조작할 수 있어 디버깅이 쉬웠고, 메모리 효율적이었다.

뭔가 재귀호출은 문제를 더 작은 단위로 쪼개 해결하는 사고방식을 길러주는 듯 하다.

효율성을 고민하지 않고 문제를 해결하는데만 집중하다보면 코드의 성능이 나빠질 수 있으니

이렇게 재귀를 잘 이해한 뒤에는 알고리즘도 더 잘 이해할 수 있을 것 같다.

그래도 이렇게 문제를 직관적으로 해결하는 강력한 도구인 것은 알겠지만,

메모리와 성능을 신경써야하는 건 꼭 기억하자.

적절히만 사용한다면 반복문으로 해결하기 복잡한 문제를 깔끔하게 해결할 수 있을테니..!