순환(Recursion)의 개념과 기본 예제 2

순환적으로 사고하기(Recursive Tihnking)

- 순환은 수학 함수 뿐만 아니라 다른 많은 문제들을 해결할 수 있다.

---

문자열의 길이 계산

public static int length(String str) {
    if (str.equals("")) return 0;
    else return 1 + length(str.substring(1));
}

---

문자열의 프린트

public static void printChars(String str) {
    if (str.length() == 0) return;
    else {
        System.out.print(str.charAt(0));
        printChars(str.substring(1));
    }
}

---

문자열을 뒤집어 프린트

public static void printCharsReverse(String str) {
    if (str.length() == 0) return;
    else {
        printCharsReverse(str.substring(1));
        System.out.print(str.charAt(0));
    }
}

---

2진수로 변환하여 출력

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

---

배열의 합 구하기

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

---

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

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

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

- 그 역도 성립한다. 즉, 모든 반복문은 순환 함수로 표현 가능하다.

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

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