재귀함수, 주먹구구식 알고리듬, P, NP

큰 문제를 반복 적용 가능한 작은 문제로 나눠 푸는 방법
모든 재귀함수는 반복문으로 작성 가능

장점

가독성이 좋음
코드가 짧음
각 단계의 변수 상태 자동 저장 (함수의 스택 프레임)
코드 검증 쉬움

단점

재귀적 문제 분석이 쉽지 않고 설계가 직관적이지 않음
원하는 결과가 나온다는 맹목적인 믿음 필요
스택 오버플로우 발생
함수 호출에 따른 과부하

간단한 예 피보나치수열 (Fn = Fn-1 + Fn-2, (n > 1))

int fibonacciRecursive(int number) {
	if (number <= 1) {
    	return number;
    }
    
    return fibonacciRecursive(number - 2) + fibonacciRecursive(number - 1);
}

꼬리 호출 (tail call)

함수의 마지막에서 다른 함수를 호출
스택 프레임 : 함수에서 사용 중인 변수 값 유지, 타 함수 호출 후 반환시 스택에 저장된 값을 되돌려 사용
꼬리 호출의 경우 타 함수의 반환 값으로 더 이상의 연산이 없다
이러한 경우 스택 프레임을 만들지 않은 꼬리 호출 최적화를 하기도 한다
아래 예시는 입력값 부터 n <= 1 까지 숫자의 곱을 꼬리 호출로 표현

int factorial(int n) {
	return factorialRecursive(n, 1);
}

int factorialRecursive(int n, int fac) {
	if (n <= 1) {
    	return fac;
    }
    
    return factorialRecursive(n - 1, n * fac);
}

아직 자바 VM(virtual Machine)은 꼬리 호출 최적화를 지원하지 않아서 스택 프레임에서
제거 되지 않기 때문에 큰 수를 이용한 경우 재귀함수와 마찬가지로 스택 오버플로우가 발생한다

주먹구구식 알고리듬

효율성을 고려하지 않은 모든 가능한 경우의 수를 시도하는 알고리듬
O(n) 보다 시간 복잡도가 높은 알고리듬이 많고, O(n3) 가 넘어가는 복잡도는 고려

P 분류 (P Class)

판정 문제들을 분류하는 방법 중 하나 (예 / 아니오)
결정론적 튜링 기계에서 다항식 시간안에 풀 수 있는 모든 문제

튜링 기계

무언가를 계산하는 기계를 대표하는 가상의 장치
일반적인 알고리듬을 수행할 수 있다

결정론적 튜링 기계

어떤 명령어 실행 뒤 다음 실행할 명령어 확정
코어 하나에서 명령어를 순서대로 실행하는 것을 비유
코어 하나에서 실행되는 다항식 시간 알고리듬이 있는 문제는 P

NP 분류 (NP Class)

비결정론적 다항식 시간(NonDeterministic Polynomial Time)
Not P 아님
어떤 명령어 실행 뒤 다음 실행할 명령어가 확정되지 않음
여러 개의 다음 명령어를 병렬적으로 실행하는 기계어로 생각

NP 완전 (NP-Complete)

NP 문제의 일부이며 가장 어려운 문제
모든 NP 문제들은 NP-완전 문제로 환원 가능
다항식 시간안에 검증 가능

NP 난해

최소 NP-완전 문제만큼 어려운 문제
NP 가 아닌 문제로 다항식 시간 안에 답 검증 불가, NP 보다 복잡도가 높음

P, NP 정리하자면

P 분류 : 결정론적 튜링 기계에서 해법을 찾는데 걸리는 시간이 다항 시간인 알고리즘을 알고 있다
NP 분류 : 결정론적 튜링 기계에서 이미 있는 해법을 검증하는 것을 다항 시간안에 할 수 있다
원래 NP 문제 정의 : 비결정론적 기계에서 해법을 다항식 시간안에 찾을 수 있는 것