순환(Recursion)에 대해(2)

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

- 순환은 수학 함수 계산뿐 아니라 다른 많은 문제들을 해결할 때 도움을 줄 수 있는 사고 방식이다.

문자열의 길이 계산

- 슈도 코드

if the string is empty

return 0;

else

return 1 plus the length of the string that excludes the first character;

//원래 문자열에서 첫 번째 문자를 뺀 길이를 계산하여 거기에 1을 더한다.

- 구현

public static int length (String str) {

if (str.equals(""))

return 0;

else

return 1 + length(str.substring(1));

//substring(1)은 원래 있던 문자열에서 제일 앞 문자를 제거한 나머지 문자열을 만드는 역할을 한다.

}

- 입력받은 문자열을 순환을 이용해 출력하기

public static void printChars (String str) {

if (str.length() == 0)

return;

else { //제일 앞 글자를 출력한 후 해당 글자를 지우며 다시 printChar함수를 불러온다.

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 { //n을 2로 나눈 몫을 먼저 2진수로 변환해 반환한 후 n을 2로 나눈 나머지를 출력한다.

printInBinary(n / 2);

System.out.print(n % 2);

}

}

- 배열의 합 구하기

public static int arraySum (int n, int[] data) {

if (n <= 0)

return 0;

else //data의 인덱스를 n - 1씩 불러옴으로써 indexOutOfBoundException을 방지할 수 있다.

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으로 표현 가능하다.

- 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현할 수 있도록 만들어준다.

- 표현이 쉬운 반면 함수 호출에 따른 오버헤드가 있다는 단점이 있다. (매개변수 전달, 엑티베이션 프레임 생성 등)