✍️Today I Learned

1. 재귀 함수의 정의
2. 재귀 함수의 요건
3. 재귀 함수의 설계
4. 재귀 함수 vs 반복문

---

재귀의 정의

자기 자신을 정의하거나 호출하는 것을 말한다.
함수가 실행 중에 자기 자신을 다시 호출하는 방식의 함수를 의미한다.

📌재귀 함수 쓰이는 곳

1. 트리 순회
2. 그래프 탐색
3. 동적 계획법
4. 백트래킹

재귀 함수의 요건

1. 재귀 호출 단계
- 자기 자신을 호출하는 단계
- 보통 호출할 때마다 문제의 크기를 줄여야 한다.

2. 기저 조건
- 특정 조건이 충족되면 더이상 자기 자신을 호출하지 않고 함수를 종료해야 한다.
- 기저 조건이 없으면 무한 재귀로 스택 오버플로우 오류가 발생할 수 있다.

재귀 함수의 설계

N!을 재귀 함수로 표현

수학적 귀납법

수학적 귀납법은 도미노 효과와 유사하다.
1. 첫 번째 도미노가 넘어진다.
2. k번째 도미노가 넘어지면 k+1번째 도미노가 반드시 넘어진다. (귀납 단계)

👉재귀 함수

1. 기저 조건
   첫 번째 도미노는 스스로 넘어져야 한다. (가장 작은 문제는 직접 풀어야 한다.)
   -> 입력이 0 이나 1일 경우 1을 반환한다.
2. 재귀 호출 단계
   현재 문제를 더 작은 크기의 문제로 나누어 해결한다.
   N! = N * (N-1)!

#include <iostream>
using namespace std;

// 팩토리얼을 구하는 재귀 함수
int Fact(int N) {
    if (N == 0 || N == 1) return 1; // 종료 조건 (0! = 1)
    return N * Fact(N - 1); // 재귀 호출
}

int main() {
    int num = 5;
    cout << num << "! = " << Fact(num) << endl;
    return 0;
}

/*
출력 결과:
5! = 120
*/

재귀 함수 동작 시 메모리의 모습

1. 함수가 호출될 때마다 지역 변수, 매개 변수, 반환 주소 등의 정보들이 메모리에 저장된다.
   이때 생성되는 메모리 블록 = 스택 프레임
   재귀 함수가 반복적으로 호출될 경우 호출마다 새로운 스택 프레임이 생성되어 스택 메모리에 쌓인다.
   메모리 한도를 초과하는 경우 스택 오버플로우 예외 발생

2. 마지막까지 호출이 완료되면, 각 함수는 자신을 호출했던 위치로 돌아가며 종료된다.
   이때 반환 주소가 사용되며, 자신을 호출한 함수의 코드 위치를 가리킨다.

3. 재귀 호출의 결과가 역방향으로 계산되어 최종 결과가 도출된다.

재귀를 사용하는게 효율적인 경우

1. 스택을 사용하는 경우
   함수 호출 과정은 스택구조 (Last In First Out) 이므로 명시적인 스택 자료구조 없이도 재귀 호출로 스택 기반 알고리즘을 구현할 수 있다.

2. 분할 정복 알고리즘으로 해결하는 문제의 경우
   분할 정복 알고리즘: 문제를 작게 나누고 동일한 방법으로 해결한 뒤 결과를 결합하여 전체 문제를 푸는 방식
   📌문제 해결 단계
   1. 분할: 문제를 더 작은 부분으로 나눈다.
   2. 정복: 각 부분을 재귀적으로 해결한다.
   3. 결합: 부분 문제의 해를 합쳐서 원래 문제를 해결한다.
   재귀 함수를 사용한 DFS 예시

#include <iostream>
#include <vector>
using namespace std;

// 그래프를 인접 리스트로 표현
vector<int> graph[9];
bool visited[9];

// DFS 함수 정의
void DFS(int node) {
    visited[node] = true;
    cout << node << ' ';
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (!visited[next]) {
            DFS(next);
        }
    }
}

int main() {
    // 그래프 초기화
    graph[1] = {2, 3, 8};
    graph[2] = {1, 7};
    graph[3] = {1, 4, 5};
    graph[4] = {3, 5};
    graph[5] = {3, 4};
    graph[6] = {7};
    graph[7] = {2, 6, 8};
    graph[8] = {1, 7};

    // DFS 실행
    DFS(1);

    return 0;
}

/*
출력 결과:
1 2 7 6 8 3 4 5
*/

재귀 사용 시 조심해야 하는 부분

함수가 과도하게 호출되지 않도록 주의해야 한다.
중복되는 함수 호출을 줄여야 한다. -> 이미 한 번 계산된 값은 어디에 저장해야 한다.
단순 재귀를 사용한 피보나치 수열 계산

#include <iostream>
using namespace std;

// 피보나치 수열을 재귀적으로 계산하는 함수
int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

int main() {
    int n = 10;
    cout << "fibo(" << n << ") = " << fibo(n) << endl;
    return 0;
}

/*
출력 결과:
fibo(10) = 55
*/

메모이제이션

한 번 계산한 결과를 저장하여 이후에 다시 계산하지 않는 기법이다.
메모이제이션을 사용한 피보나치 수영 계산

#include <iostream>
#include <vector>
using namespace std;

// 메모이제이션을 위한 배열 초기화
vector<int> memo(1000, -1);

// 피보나치 수열을 메모이제이션을 활용하여 재귀적으로 계산하는 함수
int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibo(n - 1) + fibo(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    cout << "fibo(" << n << ") = " << fibo(n) << endl;
    return 0;
}

/*
출력 결과:
fibo(10) = 55
*/

재귀 함수 vs 반복문

특성	재귀 함수	반복문
정의	자기 자신을 호출하여 작업을 수행	for, while 등의 제어 구조를 사용하여 작업을 반복 수행
메모리 사용	각 함수 호출 시 스택 메모리를 사용.	스택 메모리 사용 X.
	호출이 깊어지면 스택 오버플로우가 발생 가능	메모리 사용이 효율적이다.
실행 속도	함수 호출과 복귀를 위한 컨텍스트 스위칭으로	일반적으로 빠르다.
	인해 반복문보다 느릴 수 있다.
가독성	코드가 간결. 가독성 ↑	코드가 길어질 수 있다.
		많은 변수를 사용하게 되어 가독성 ↓
변수 사용	상태 유지를 위해 추가적인 변수를 사용 X.	상태 유지를 위해 여러 변수를 사용해야 할 수 있다.
무한 반복 시	종료 조건을 잘못 설정하면 스택 오버플로우 발생	종료 조건을 잘못 설정하면 CPU를 계속 사용해
		시스템에 부하를 줄 수 있다.