재귀함수(Recursive Function) 란?Permalink

특정 조건(= 끝나는 조건)이 될 때까지 자기자신을 계속 호출하는 함수이다.
함수 안에 끝나는 조건이 있고, 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);
}

소스보기Permalink

package com.onda2me.algorithm.step2;

/*

재귀함수란?
특정 조건(= 끝나는 조건)이 될 때까지 자기자신을 계속 호출하는 함수이다.
함수 안에 끝나는 조건이 있고, return에서 자기 자신을 호출한다.

### 문제설명
주어진 문자열을 For문과 재귀함수를 이용하여 거꾸로 출력하는 함수를 각각 만들어 비교한다.

*/

public class Function02Recursive {    
   
    public static void main(String[] args) {

        solution("abcdef");
    }

    public static void solution(String str) {

        System.out.println("--------------------");
        System.out.println("f("+str+") = "+ reverse(str) ); 
        
        System.out.println("--------------------");
        System.out.println("r("+str+") = "+ reverse(str.toCharArray(), str.length()-1));        
    }
    

    /**
     * for문을 이용하여 문자열을 거꾸로 출력
     * 예) abcdef -> fedcba
     * 
     * @param str
     * @return
     */
    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();
    }

    /**
     * 재귀함수를 이용하여 주어진 문자열을 거꾸로 출력
     * 예) abcdef -> fedcba
     * 
     * r(1) = a
     * r(2) = b + r(1) = ba
     * r(3) = c + r(2) = cba
     * r(4) = d + r(3) = dcba
     * r(5) = e + r(4) = edcba
     * r(6) = f + r(5) = fedcba
     * 
     * @param arr
     * @param n
     * @return
     */
    public static String reverse(char arr[], int n) {
        
        if(n < 0)
            return "";

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

}

                

실행결과Permalink