재귀함수(Recursive Function) 란?

특정 조건(= 끝나는 조건)이 될 때까지 자기자신을 계속 호출하는 함수이다.
함수 안에 끝나는 조건이 있고, return에서 자기 자신을 호출한다.
재귀함수는 같은 규칙을 가지는 함수를 반복해서 사용할 경우 적용할 수 있다.

이번 글에서는 주어진 문자열을 For문과 재귀함수를 이용하여 거꾸로 출력하는 함수를 각각 만들어 본다.

for문을 이용한 방법

for문을 이용한 구현 방법은 문자열 끝에서부터 한글자씩 읽어 StringBuilder에 저장하여 문자열을 모두 읽은 뒤 출력하면 된다.

public static String reverse(String str) {

        StringBuilder bld = new StringBuilder();

        // 문자열 끝에서부터 한글자씩 읽어서 저장
        for(int i=0; i<str.length(); i++) {

            bld.append(str.substring(str.length()-1-i, str.length()-i));
        }
        return bld.toString();
}

재귀함수로 구현하기 위해 거꾸로 문자열 출력에도 일반화 할 수 있는 규칙을 찾아본다.

r(1) = a
r(2) = b + r(1) = ba
r(3) = c + r(2) = cba
r(4) = d + r(3) = dcba

r(n) = n + r(n-1)

재귀함수를 이용한 방법

public static String reverse(char arr[], int n) {
    
    if(n < 0)
        return "";

    return arr[n] + reverse(arr, n-1);
}

소스보기

소스로딩 실패

실행결과