[개념정리] 재귀 알고리즘

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 '재귀적' 이라고 함.

 

직접 재귀와 간접 재귀

직접 재귀란 자신과 같은 함수를 호출하는 것.

간접 재귀란 함수 a가 함수 b를 호출하고, 다시 함수 b가 함수 a를 호출하는 구조이다.

 

재귀 알고리즘에 알맞은 경우

- 풀어야 할 문제가 재귀로 정의되는 경우

- 계산 할 함수가 재귀로 정의되는 경우

- 처리할 데이터 구조가 재귀로 정의되는 경우

유클리드 호제법

최대공약수는 y가 0이면 x이고, y가 0이 아닐 경우 gcd(y, x%y) 이다.

 

하향식 분석과 상향식 분석

하향식 분석이란 가장 위쪽의 함수 호출부터 시작해 계단적으로 자세히 조사해 가는 분석 기법으로 같은 함수의 호출이 여러번 나올 수 있기 때문에 경우에 따라 효율적이지 않을 수 있다.

상향식 분석이란 아래쪽부터 쌓아 올리며 분석하는 방법이다.

 

하노이의 탑

하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제로 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮긴다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

출처 : https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

8퀸 문제

8퀸 문제 : 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.

퀸 : 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능.

출처 : https://stackoverflow.com/questions/63536411/how-to-rotate-a-solution-to-the-8-queens-puzzle-by-90-degrees

[규칙1] : 각 열에 퀸을 1개만 배치합니다.

[규칙2] : 각 행에 퀸을 1개만 배치합니다.

 

분할 해결법

분할 해결법이란 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법.

 

한정 조작

분기를 없애 불필요한 조합을 줄이는 방법.

분기 한정법

가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법.