자바 - 28 (재귀(Recursion) 알고리즘)

● 재귀(Recursion) 알고리즘

- 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결하는 함수
- 프랙탈과 유사
- 끝나는 지점이 있거나, 정리가 가능할때 사용하기

 

* 프랙탈(fractal)은 일부 작은 조각이 전체와 비슷한 기하학적 형태(자기 유사성)

▶ 실습 
package : bbs.recursion

▷class : HelloRecursion

* 디버그
중단점 - System.out.println("안녕하세요, 재귀예요."); 

 

-> 본인을 계속 호출하면서 무한반복

StackOverflowError

▷ class : HelloRecursion2

- 종료지점 설정

package bbs.recursion;

public class HelloRecursion2 {

	// 재귀함수 호출시 재귀횟수가 줄어감에 따라 마지막 값에 도달하면 재귀를 종료하고 빠져나갈 수 있다. 
	public static void main(String[] args) {
		function(5);

	}
	
	public static void function(int exitNum) {
		if(exitNum == 0) {
			return;
		} else {
			System.out.printf(
					"안녕하세요, (%d == 0)이면 마칠수 있어요.\n", exitNum);
			
			// exitNum - 1 : 재귀호출을 제어함 (빠져나가는 이유)
			function(exitNum - 1);
		}
		
		
	}

}

* 디버그
중단점 - if(exitNum == 0) 
-> 5번 호출하면 종료

-> exitNum = 0이 되어 종료

▷ 1 ~ 100까지 합 구하기
1. 기본 방식으로 만들기
class : CalcApp

package bbs.recursion;

public class CalcApp {

	public static void main(String[] args) {
	
		int total = sum(1, 100);
		System.out.println("1 + ... + 100 = " + total);

	}

	public static int sum(int start, int end) {
		int total = 0;
		for(int i = start; i <= end; i++) { // 100까지 돌아야하므로 <=
			total = total + i;
		}
		
		return total;
	}
}

2. 재귀로 만들기
class : CalcRecursionApp

package bbs.recursion;

public class CalcRecursionApp {

	public static void main(String[] args) {
		// 재귀를 이용하여 자기보다 작은 수를 계속 불러 
		// 마지막 더 이상 재귀가 되지 않는 값이 계산되면 그 이전 자기값이 된다.
		System.out.println(sum(100)); // 100(자신) + sum(99)
				  // sum(99) = 99 + ... + 1
				  // sum(99) = 99 + sum(98)
				  //       ...
				  // sum(2) = 2 + sum(1)
				  // sum(1) = 1
		
	}
	
	public static int sum(int num) {
		// num 더하는 값
		if (num == 1) {
			return 1;  // sum(1) = 1
		} else {
			// 자기자신 수 + 자기자신 수보다 작은 수의 합
			return num + sum(num - 1);
		}
	}

}

- 큰 곳에서 작은 곳으로 흐름(1일때 중단하기 설정)

if (num == 1) {
	return 1;  // sum(1) = 1
}

- return : 재귀를 호출하는 값(이전 값) + 작아지는 값

* 디버그
중단점 - if (num == 1)

-> 재귀는 많은 메모리를 차지하므로 번거로움

return 1;
-> 많은 반복하지 않아도 됨

 

* 의문점

- 중단점의 차이? 

return 1;을 중단점으로 설정하면 sum(100) ~ sum(1)까지의 식을 아래와 같이 한번에 풀어서 해석한다

* 쓰레드에 내용에는 해당 내용이 담겨있다

sum(100) = 100 + sum(99)
sum(99) = 99 + sum(98)
       ...
sum(2) = 2 + sum(1)
sum(1) = 1

이렇게 되면 바로 sum(1)의 값을 알 수 있기 때문에 sum(1)의 값으로 sum(2)를 계산하고 ...sum(99)의 값으로 sum(100)을 계산하면 효율적인 디버그를 할 수 있다.

 

if (num == 1)을 중단점으로 설정하면 if문에 대한 판단을 먼저 진행해야하기 때문에 더욱 많은 반복을 하게 된다

-> sum(100) = 100 + sum(99) ~ sum(1) = 1까지의 식을 하나하나 진행해야함

쓰레드를 sum(100)부터 만들어서 sum(1)까지 도달을 하여야 sum(1)의 값을 알게되어서 sum(2)의 값을 알 수 있고  sum(3)의 값을 알아야 sum(4) ... sum(100)의 값을 알 수 있다.

그렇기 때문에 더욱 복잡한 디버그가 된다!

 

---

● 쓰레드(thread) - 나중에 자세히

* main() 메소드 종료 == 메인쓰레드 종료
일반적으로 메인쓰레드가 종료하면 프로그램이 종료된다.
* 쓰레드란 프로그램의 처리흐름을 말한다
* 프로그램을 실행하면 운영체제가 프로세스라고 하는 처리흐름을 만든다.
프로새스는 CPU의 작업과 메모리를 할당받아 프로그램의 코드를 한줄씩 실행한다.
이때 프로세스의 프로그램코드를 실행하는 하나의 실행흐름을 쓰레드라고 한다.
이 쓰레드를 자바에서는 메인쓰레드라고 부른다.
* 메인쓰레드만 가지고 모든 일을 처리할 수 없다
엑셀처럼 계산하는 부분과 화면에 그래프를 그리는 부분, 파일을 인쇄하는 부분처럼 동시에 여러가지 일을 실행하는 경우가 더 많다
이런 처리흐름을 메인쓰레드와 작업쓰레드 UI쓰레드라고 한다
* 엑셀프로그램을 실행한 흐름이 메인쓰레드
표를 계산하는 흐름이 시간이 제일 많이 걸리므로 작업쓰레드가 됨
프린트를 인쇄하는 경우에도 별도로 출력하고 있으므로 작업쓰레드
화면에 그래프를 그리는 부분은 끊김이 없이 일정순간마다 새로 그려저야하므로 UI쓰레드
UI쓰레드는 작업쓰레드와 통신을 함