[알고리즘/인프런정리] 1-2. Recursive Thinking

Recursive Thinking 순환적 사고하기

 

Recursion은 수학함수 계산에만 유용한가?

-> 다른 많은 문제들도 해결할 수 있다.

 

- 문자열의 길이 계산

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

 

- 문자열의 프린트

public static int printChars(String str) {
	if(str.equals(""))	// base case
    	return 0;
    else {
    	System.out.print(str.charAt(0));
    	return 1+length(str.substring(1));
    }
}

 

- 2진수 변환 출력

public static int printInBinary(int n) { // 2진수 변환 출력
	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);
    }
}

 

Recursion vs Iteration

-  모든 순환함수와 반복문은 서로 표현이 가능하다.

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

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

  경우에 따라 순환함수로 단순히 표현해야 하는 경우도 있기 때문에 사용한다.

 

 

Q. 액티베이션 프레임 생성 ?? -> 검색해도 안나온다. 누가 알려주세요 ㅠㅠ