초코레

재귀 알고리즘에 대한 예제로 자주 등장하며 문제는 아래와 같다. 서로 공격하여 잡을 수 없도록 8개의 퀸를 8 x 8 체스판에 놓으세요. (퀸은 서 있는 지점에서 체스판으로 어떤 지점으로든 여덟 방향으로 직선 이동이 가능하다.) 퀸을 배치하기 위해 다음과 같은 규칙을 세울 수 있다. [규칙 1] : 각 열에 퀸을 1개만 배치한다. → 가지 뻗기로 퀸을 배치하는 조합을 나열 [규칙 2] : 각 행에 퀸을 1개만 배치한다. → 분기를 한정하기 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라고 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method)이라고 한다. 1 2 3 4 5 6 7 8 9..

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여있고 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 한다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다. 3개의 기둥을 각각 시작 기둥, 중간 기둥, 목표 기둥이라고 부르고, 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 가장 먼저 그룹(가장 큰 원반을 제외한 원반들)을 중간 기둥으로 옮겨야 한다. 다시 그룹 중에서 가장 큰 원반을 제외한 원반을 그룹으로 보고 같은 방식으로 옮긴다. 이 방식으로 반복하여 원반이 N개인 하노이의 탑 문제를 해결할 수 있다. 123456789101112131415//하노이의 탑publi..

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다. 재귀는 병합 정렬과 퀵 정렬, 이진검색트리 등에 사용된다. 재귀의 사용 예로 양의 정수의 팩토리얼 (n!)을 들 수 있다. 예를 들어 10의 팩토리얼인 10!은 10 * 9!로 구할 수 있고 그 우변에서 사용되는 식 9!은 9 * 8!로 구할 수 있다. 메서드가 자신을 다시 호출하는 방식을 재귀 호출(recursive call)이라고 한다. 직접 재귀 : 자신과 같은 메서드를 내부에서 다시 호출하는 것 간접 재귀 : 다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것 a()에서 b() 호출 → b()에서 a() 호출 → a()에서 b() 호출 1 2 3 4 5 6 7 8 9 10 11 //팩토리얼을 재귀적으..