Recursion의 개념과 기본 예제들 2

Recursive Thinking 

순환적으로 사고하기!

 

Recursion은 수학 함수 계산에만 유용할까?

 

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

recursion으로 해결할 수 있다.

 

for문 대신에 recursion을 통해 해결 할 수도 있다.

 

---

문자열의 길이 계산

 

라이브러리 함수를 써도 되지만 

라이브러리 함수는 어떻게 동작할까?

 

앞에서부터 문자하나하나씩 세면 된다.

이것이 절차적인 프로그램이라고도 이야기할 수 있다.

 

for문 같은 반복문을 통해 해결 할 수 있지만

 

문자열의 길이가 0이라면 리턴하고(base case)

그렇지 않다면 

원래 문자열에서 첫번째 문자열을 제거한 그 문자열의 길이를 제거하고

1을 더하면 된다.

 

public static int length(String str){
	if(str.eqauls(""))
    	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));
        }
}

else문 안에서 순서만 바꾸어 주면 가능한 문제이다.

 

---

2진수로 변환하여 출력

 

 

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

음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.

n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후

n을 2로 나눈 나머지를 인쇄한다.

 

---

배열의 합 구하기

 

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

data[0]에서 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으로 표현 가능하다.

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

하지만 함수 호출에 따른 오버헤드가 있다.