[Algorithm] 재귀(Recursion) 02

Recursion을 이용해 다양한 문제 풀기

수학함수뿐 아니라 다른 많은 문제들을 

recursion으로 해결할 수 있다.

 

 

문자열의 길이 계산

public class Test01 {
    public static void main(String[] args) {
        System.out.println(length("Hello")); // 5
    }

    public static int length(String str) {
        if (str.equals(""))
            return 0;
        else
            return 1 + length(str.substring(1));  // 1 + 첫글자를 제외한 문자열의 길이 
    }
}

 

 

문자열의 프린트

public class Test02 {
    public static void main(String[] args) {
        printChars("Hello");
    }

    public static void printChars(String str) {
        if (str.length() == 0)
            return;
        else {
            System.out.println(str.charAt(0));
            printChars(str.substring(1)); // 0번째 문자열 제외한 문자열
        }
    }
}

 

 

문자열을 뒤집어 프린트

public class Test03 {
    public static void main(String[] args) {
        printCharsReverse("Hello");
    }

    public static void printCharsReverse(String str) {
        if (str.length() == 0)
            return;
        else {
            printCharsReverse(str.substring(1)); // 첫 번째 문자열 제외한 문자열
            System.out.println(str.charAt(0));
        }
    }
}

 

 

2진수로 변환하여 출력

public class Test04 {
    public static void main(String[] args) {
        printInBinary(10); // 1 0 1 0
    }

    public static void printInBinary(int n) {
        if (n < 2)
            System.out.println(n);
        else {
            printInBinary(n/2);
            System.out.println(n%2); 
        }
    }
}

 

 

배열의 합 구하기

data [0]에서 data [n-1]까지의 합 구하기

public class Test05 {
    public static void main(String[] args) {
        System.out.println(sum(2, new int[]{1, 2, 3})); // -> 1 + 2 -> 3
    }

    public static int sum(int n, int[] data) {
        if (n == 0)
            return 0;
        else
            return sum(n - 1, data) + data[n - 1];
    }
}

 

 

데이터파일로 부터 n개의 정수 읽어오기

Scanner in이 참조하는 파일로부터 n개의 정수를 입력받아 

배열 data의 data[0]...data[n-1]에 저장한다.

public void readFrom(int n, int[] data, Scanner in) {
        if (n == 0)
            return;
        else{
            readFrom(n-1, data, in);
            data[n-1] = in.nextInt();
        }
    }

 

 

---

Recursion vs Iteration ?

모든 순환함수는 반복문(iteration)으로 변경 가능하다.

그 역도 성립한다. 즉, 모든 반복문은 recursion으로 표현 가능하다!

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현이 가능하다.

하지만 함수 호출에 따른 오버헤드가 있다. (매개변수 전달, 액티베이션 프레임 생성 등)

 

그때그때 상황에 맞게 반복문과 순한함수를 사용하면 좋을 것 같다!