# 재귀 알고리즘 (Recursive)


## 재귀 알고리즘이란?

- 자신이 수행할 작업을 처리하는 도중에 자기 자신을 호출하여 작업을 수행하는 알고리즘
- 함수나 프로시저가 자기 자신을 호출하는 것
- 재귀 알고리즘은 깊이가 무한정하게 들어갈 수 있으며, 무한루프에 빠질 가능성도 있으므로 조심해서 사용해야 한다
- 장점
- 코드가 간결하고 이해하기 쉽다
- 명확하게 해결하고자 하는 문제를 표현하기 쉽다
- 단점
- 재귀 알고리즘은 반복문보다 실행 속도가 느릴 수 있다
- 함수 호출에 따른 메모리 공간이 필요하므로 메모리 사용량이 증가할 수 있다
- 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있다
- 재귀 호출이 무한루프에 빠질 가능성이 있으므로, 종료 조건을 반드시 설정해야 한다

## 재귀 알고리즘 예시

1. 팩토리얼 계산 문제
- 정수 N이 주어졌을 때, N!을 계산하는 문제
2. 피보나치 수열 문제
- 정수 N이 주어졌을 때, 피보나치 수열의 N번째 항을 구하는 문제
3. 이진 검색 문제
- 정렬된 배열과 찾고자 하는 값이 주어졌을 때, 이진 검색을 이용하여 해당 값의 인덱스를 구하는 문제
4. 하노이의 탑 문제
- N개의 원판이 있는 탑이 있을 때, 모든 원판을 다른 기둥으로 옮기는 문제
- 백준 알고리즘 1914번 ==[링크](https://www.acmicpc.net/problem/1914)==
5. 최대공약수 문제
- 두 수가 주어졌을 때, **유클리드 호재법**을 이용하여 최대공약수를 구하는 문제

> 재귀 문제는 반복문으로 대체가 가능하다. 반복문이 아닌 재귀를 사용할 경우 메모리 측면에서 비효율적이기 때문에 알고리즘 문제를 풀 때 적합한 방법은 아니다.

### 하노이탑 문제

- 백준 알고리즘 1914번 ==[링크](https://www.acmicpc.net/problem/1914)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 하노이탑 문제 수도코드 예

1. 원판의 개수 N을 입력받는다.
2. 최소 이동 횟수를 계산한다 (2^N - 1).
3. 최소 이동 횟수를 출력한다.
4. 원판 개수가 20개 이하인 경우 이동 과정을 출력한다.
5. 하노이 탑 알고리즘을 구현한다 (재귀 함수).
    a. 이동할 원판이 없는 경우 반환한다.
    b. N-1개의 원판을 출발 기둥에서 보조 기둥으로 이동한다 (하노이 탑 알고리즘 호출).
    c. N번째 원판을 출발 기둥에서 도착 기둥으로 이동한다.
    d. N-1개의 원판을 보조 기둥에서 도착 기둥으로 이동한다 (하노이 탑 알고리즘 호출).

#### 하노이탑 문제 소스코드 예

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 원판의 개수 입력

        // 최소 이동 횟수 계산 및 출력
        BigInteger minMoves = BigInteger.valueOf(2).pow(N).subtract(BigInteger.ONE);
        System.out.println(minMoves);

        // 원판 개수가 20개 이하인 경우 이동 과정 출력
        if (N <= 20) {
            hanoi(N, 1, 2, 3);
        }
    }

    // 하노이 탑 알고리즘 구현
    public static void hanoi(int N, int from, int aux, int to) {
        if (N == 0) return; // 이동할 원판이 없는 경우 반환

        hanoi(N - 1, from, to, aux); // N-1개의 원판을 출발 기둥에서 보조 기둥으로 이동
        System.out.println(from + " " + to); // N번째 원판을 출발 기둥에서 도착 기둥으로 이동
        hanoi(N - 1, aux, from, to); // N-1개의 원판을 보조 기둥에서 도착 기둥으로 이동
    }
}

### 최대공약수 구하기

#### 유클리드 호제법(Euclidean algorithm)


- 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘
- 원리
- 두 수 a와 b (a > b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다
- 즉, `GCD(a, b) = GCD(b, a % b)`가 성립한다
- 예시 : `a = 56`이고 `b = 48`일 때
1. `GCD(56, 48) = GCD(48, 56 % 48) = GCD(48, 8)`
2. `GCD(48, 8) = GCD(8, 48) = GCD(8, 48 % 8) = GCD(8, 0)`
3. b가 0이 되었으므로, a와 b의 최대공약수는 8이다

#### 최대공약수 구하기 수도코드 예

1. 두 수 A와 B를 입력받는다.
2. B가 0이 될 때까지 다음 과정을 반복한다.
    a. A를 B로 나눈 나머지를 R이라고 한다.
    b. A에 B의 값을, B에 R의 값을 할당한다.
3. A의 값을 반환한다.

#### 최대공약수 구하기 소스코드 예 (재귀 사용)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(); // 첫 번째 수 입력
        int B = sc.nextInt(); // 두 번째 수 입력
        System.out.println(gcd(A, B)); // 최대공약수 출력
    }

    public static int gcd(int A, int B) {
        if (B == 0) return A; // B가 0이면 A를 반환
        return gcd(B, A % B); // GCD(B, A % B)를 반환
    }
}

#### 최대공약수 구하기 소스코드 예 (반복문 사용)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(); // 첫 번째 수 입력
        int B = sc.nextInt(); // 두 번째 수 입력
        System.out.println(gcd(A, B)); // 최대공약수 출력
    }

    public static int gcd(int A, int B) {
        while (B != 0) {
            int R = A % B;
            A = B;
            B = R;
        }
        return A;
    }
}

#### 최소공배수를 구하는 방법

- 유클리드 호제법을 사용하여 최대공약수를 구했다면, 최소공배수(LCM, Least Common Multiple)도 쉽게 구할 수 있다.
- `LCM(A, B) = A * B / GCD(A, B)` 공식을 이용하면 된다.

#### 최소공배수 구하기 수도코드 예

1. 두 수 A와 B를 입력받는다.
2. 최대공약수를 구하는 함수를 호출하여 최대공약수를 구한다.
3. 최소공배수를 계산하여 출력한다.

#### 최소공배수 구하기 소스코드 예

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(); // 첫 번째 수 입력
        int B = sc.nextInt(); // 두 번째 수 입력
        int GCD = gcd(A, B); // 최대공약수 계산
        int LCM = A * B / GCD; // 최소공배수 계산
        System.out.println(LCM); // 최소공배수 출력
    }

    public static int gcd(int A, int B) {
        while (B != 0) {
            int R = A % B;
            A = B;
            B = R;
        }
        return A;
    }
}