[Algoritm] 재귀 알고리즘

1. 재귀 알고리즘

재귀 알고리즘의 바탕이 되는 기본 개념은 '어떤 문제를 해결하기 위해 문제의 범위보다 좁은 하위 문제를 해결하고, 그 하위 문제의 해답을 이용하여 원래 문제를 해결한다.' 이다.

재귀 함수는 자기 자신을 참조하는 함수이다. 원래의 문제를 동일한 유형의 하위 문제로 나누고 하위문제를 해결한 다음 결과와 결합한다. 이러한 알고리즘을 분할 정복법 이라 한다.

또 하위 결과를 저장하여 조회하는 알고리즘이 추가되면 동적프로그래밍이라고 부른다.

이러한 재귀 함수는 다음과 같은 구조를 가져야 한다.

• Base Case : 재귀함수의 종료 조건으로 더 이상 문제를 쪼갤수 없을 때, 자기자신을 호출하지 않고 답이 나올 때
• Recusion Case: 복잡한 입력을 더 간단한 입력으로 분류하여 자기자신을 호출

Q. 문제: 주어진 문자열로 만들 수 있는 수의 조합을 모두 찾으시오.

이 문제는 다양한 방법으로 해결 할 수 있다.
재귀호출, dfs, bfs 등 모든 경우의수를 탐색하는 알고리즘을 사용하면 된다.

근데 사실 dfs와 bfs는 완전탐색하기 위해 재귀함수를 사용한다.
함수의 목적 및 형태에 따라 재귀 함수로 구성된 코드가 다양한 알고리즘으로 불릴 수 있다.

이번 글에서는 문자열을 prefix와 suffix로 나누어서 하위 문제를 해결하는 재귀 함수를 만들어서 해결할 것이다.

import java.util.HashSet;

class Solution {

    public static void main(String[] args) {
        String numbers = "17";
        HashSet<Integer> hashSet = new HashSet<Integer>(); // 조합을 담을 hashSet (중복을 허용하지 않기 위해 Set을 사용)
        getHashSet("", numbers, hashSet);
        System.out.println("[hashSet]:" + hashSet.toString());
    }

    public static void getHashSet(String prefix, String suffix, HashSet<Integer> hashSet) {
        if (!"".equals(prefix)) {
            hashSet.add(Integer.parseInt(prefix));
        }

        for (int i = 0; i < suffix.length(); i++) { // Base Case - 나중에 suffix가 ""이 되도록 소스를 구성 했기 때문에 종료됌
            StringBuilder prefixSb = new StringBuilder();
            StringBuilder suffixSb = new StringBuilder();
            prefixSb.append(prefix);
            prefixSb.append(suffix.charAt(i));
            suffixSb.append(suffix.substring(0, i));
            suffixSb.append(suffix.substring(i + 1, suffix.length()));
            getHashSet(prefixSb.toString(), suffixSb.toString(), hashSet); // Recusion Case - 문제를 간단한 입력으로 분류하여 자기자신을 호출
        }
    }
}

결과 => [hashSet]:[1, 17, 7, 71]

참고사이트

https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/properties-of-recursive-algorithms