Recursion의 개념과 기본 예제들 - 2

1. 문자열의 길이 계산

1) Base Case : 문자열 값이 null 인 경우 → return 0;

2) Recursive Case : 첫번째 문자를 제외한 길이 + 1을 return 한다.

 
public class RecursionTest {
	public static void main(String[] args) {
		System.out.println(length("test"));
	}
	
	public static int length(String str){
		if(str.equals(""))
			return 0;
		else
			return 1+length(str.substring(1)); // 차례대로 est -> st -> t  return
	}
}

2. 문자열을 뒤집어 프린트

 
public class RecursionTest {
	public static void main(String[] args) {
		printCharsReverse("test");
	}
	
	public static void printCharsReverse(String str){
		if(str.length()==0)
			return;
		else{
			printCharsReverse(str.substring(1));
			System.out.print(str.charAt(0));
		}
	}
}

/*
결과값: tset
*/

3. 2진수로 변환하여 출력

 public class RecursionTest {
	public static void main(String[] args) {
		printInBinary(9);
	}
	
	public static void printInBinary(int n){
		if(n<2)
			System.out.print(n);
		else{
			printInBinary(n/2); // n을 2로 나눈 몫을 먼저 2진수로 반환하여 인쇄한 후
			System.out.print(n%2); //n을 2로 나눈 나머지를 인쇄한다.
		}
	}
}

4. Recursion vs Iteration

• 모든 순환함수는 반복문(iteration)으로 변경 가능하다.
• 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.
• 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
• 하지만 함수 호출에 따른 오버해드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)