[Algorithm] 재귀 호출(Recursion)

#. 재귀 호출

  ㅇ 재귀 호출(=재귀 함수) recursion(=recursive function)

    - 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

    - 다양한 알고리즘을 구현하는데 매우 유용하게 사용할 수 있는 도구

    - 문제의 특성에 따라 재귀 호출은 코딩을 헐씬 간편하게 해 줄 수 있는 강력한 무기

    - 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성

    - 완전 탐색을 구현할 때 아주 유용한 도구

  ㅇ 완전 탐색으로 해결하기 위해 필요한 과정

    1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수가 정확히 비례

     - 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지 가늠

    2. 가능한 든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔

     - 각 선택은 답의 후보를 만드는 과정의 한 조각이 됨

    3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성

    4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로 이것을 기저 사례로 선택해 처리

   

    ex 1) 1부터 n까지의 합을 반환하는 함수 구현

      - 모든 재귀 함수는 '더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 함

      - 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호풀의 기저 사례(base case)라고 함

public class C61 {
    // 1. for문을 사용할 경우
    private static int sum(int n){
        int ret = 0;
        for (int i = 1; i <= n; ++i){
            ret += i;
        }
        return ret;
    }
    // 2. 재귀 호출을 사용할 경우
    private static int recursiveSum(int n){
        if (n == 1)    return 1;
        return n + recursiveSum(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println(sum(7));
        System.out.println(recursiveSum(7));
    }
}
 

        sol 1. for문을 사용

                       - 골라야 할 원소의 수가 늘어날 수록 반복문도 늘어남

1 2 3 4 5 6 7 8 9 10 11

int n=10;   for(int i=0; i<n; i++) {     for(int j=i+1; i<n; j++) {         for(int k=j+1; i<n; k++) {             for(int l=k+1; l<n; l++) {                 System.out.println(i + " " + j + " " + k + " " + l);             }         }     } } Colored by Color Scripter

cs

        sol 2. 재귀 함수로 구현

      - 재귀 호출은 이런 경우 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있게 해줌

      - 수행할 작업을 조각으로 나눈 후 남은 원소들을 고르는 작업

        ㄴ 원소들의 총 개수

        ㄴ 더 골라야 할 원소들의 개수

        ㄴ 지금까지 고른 원소들의 번호

import java.util.*;
 
/*
 n : 전체 원소의 수
 picked : 지금까지 고른 원소들의 번호
 toPick : 더 고를 원소의 수
 */
public class C62 {
    static int N=7;
    
    private static void pick(int n, ArrayList<Integer> picked, int toPick) {
        // 더 고를 원소가 없을 경우 고른 원소들을 출력
        if (toPick == 0) {
            printPicked(picked);
            return;
        }
        // 고를 수 있는 가장 작은 번호를 계산
        int smallest = picked.isEmpty() ? 0 : picked.get(picked.size()-1) + 1;
        // 원소를 하나 선택
        for (int next = smallest; next < n; next++) {
            picked.add(next);
            pick(n, picked, toPick-1);
            picked.remove(picked.size()-1);
        }
    }
    //picked에 저장된 원소 출력
    private static void printPicked(ArrayList<Integer> picked) {
        for(int i=0; i<picked.size(); i++) {
            System.out.print(picked.get(i) + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        ArrayList<Integer> picked = new ArrayList<Integer>();
        pick(7, picked, 4);
    }
}

#. 많이 등장하는 완전 탐색 유형

* 입력의 크기에 따라 답의 개수가 어떻게 변하는지를 알고 구현하는 방법을 연습하는 것이 좋음

  ㅇ 순열(permutation)

    - 서로 다른 N개의 원소를 일렬로 줄 세운 것

    - 가능한 순열의 수는 N!이 되는데, 

    - N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려움, 이런 경우 완전 탐색 말고 다른 방법을 생각해야 함

  ㅇ 조합(combination)

    - 서로 다른 N개의 원소 중 R개를 순서 없이 골라낸 것

    - 경우의 수는 이항 계수 C(n,k)로 정의

    - 이항 계수

      if 0<= k <= n : return n! / k!(n-k)!

      if k < 0 : return 0

      if k > n : return 0

  ㅇ 2^n 가지 경우의 수

    - n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수

    - 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 간단하게 시도 가능

#. 재귀 호출 사용하기

  ㅇ 재귀 호출의 return 값을 받아서 어떻게 처리할지 생각하기
     (ex: min, max, +=)

  ㅇ 기저 사례 생각하기

    - 일어날 수 있는 변수를 예외처리 해주기

      (ex: return false)

    - 최대한 중복을 줄일 수 있는 방법 생각하기(순서)

      (ex: 가장 앞 번호 우선, 가장 위에 있는 번호 우선)

    - 재귀 호출이 모두 완료되었을 때, 어떻게 작동할지 생각하기

      (ex: return 1, return 0)

    - 어떠한 상황에 재귀 호출을 사용할지 생각하기

--

--

--

--

참고 : 알고리즘 문제 해결 전략