[JAVA] 재귀함수 심화

다음 Java로 구현된 프로그램을 분석하여 그 실행 결과를 쓰시오.

public class Main {
	public static String rf(String str, int index, boolean[] seen) {
		if(index < 0) return "";
		char c = str.charAt(index);
		String result = rf(str, index-1, seen);
		if(!seen[c]) {
			seen[c] = true;
			return c + result;
		}
		return result;
	}
	public static void main(String[] args) {
		String str = "abacabcd";
		int length = str.length();
		boolean[] seen = new boolean[256];
		System.out.print(rf(str, length-1, seen));
	}
}

코드 분석:

1. main 메소드
   • str 문자열은 "abacabcd"입니다.
   • length = str.length()는 8을 반환합니다.
   • boolean[] seen = new boolean[256] 배열은 각 문자가 등장했는지 여부를 기록합니다. 기본값은 false입니다.
   • rf(str, length-1, seen) 호출은 문자열의 마지막 문자부터 시작하여 재귀적으로 호출됩니다.
2. rf 메소드
   • 이 메소드는 문자열을 역순으로 하나씩 탐색하면서, 중복되지 않은 문자를 결과 문자열에 포함시킵니다.
   • 중복된 문자는 결과에 포함되지 않고 무시됩니다.
   • index가 음수일 때는 더 이상 탐색할 문자가 없으므로 재귀 호출이 종료되고 빈 문자열이 반환됩니다.
3. 중복 문자 처리
   • if(!seen[c])에서 해당 문자가 아직 등장하지 않은 경우에만 결과에 추가됩니다.
   • 등장한 문자는 seen[c] = true로 기록되며 이후에는 결과에 포함되지 않습니다.

실행 과정:

문자열 "abacabcd"를 뒤에서부터 처리합니다:

• d: 처음 등장, 결과는 "d".
• c: 처음 등장, 결과는 "cd".
• b: 처음 등장, 결과는 "bcd".
• a: 처음 등장, 결과는 "abcd".
• 남은 문자들은 모두 중복되므로 추가되지 않습니다.

그러므로 역순으로 중복되지 않은 문자를 출력하여 최종 결과는 "dcba"가 됩니다.