재귀
- 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라 한다
- 코드의 간결화 및 변수 사용 최소화 장점
- 이론적으로 반복문 <=> 재귀 모두 가능
재귀에서 종료 조건은 코드로 무조건 구현되어야 한다
장점
- 직관적이고 이해하기 쉬운 문제 해결 기법
- 문제를 유사한 형태의 더 작은 문제로 축소하여 해결
- 재귀의 경우 컴퓨터 환경에서 stack 구조라 생각하면 된다
- 마지막에 호출한 함수 종료해야 이전에 호출한 함수 실행
- 때문에 단점으로 과도한 함수 호출로 인한 stack overflow 가능성과 낮은 성능(반복 알고리즘에 비해)
재귀적 정의(recursive definition)
- 자기 자신을 사용하여 정의
- ex) n! = n * (n-1)!
재귀 호출(recursive call)
- 메서드를 계속해서 맞물려 호출하는 경우
- 직접 재귀
- 자기 자신의 메서드 내부에서 자기 자신의 메서드 호출
- 간접 재귀
- 자기 자신의 메서드 내부에서 호출이 아닌 다른 메서드를 통해 자기 자신의 메서드 호출
재귀 실행 순서에 관해
재귀를 씀에 있어 메서드 실행 순서와 관련된 이슈를 겪어 찾아봄
항상 사진과 같은 구조로 사용했다
이 과정에서 순차적으로 실행된다 착각해 문제를 푸는데 이슈 발생
실질적으로 A 함수를 두번째 호출했을 때를 확대해 본다면 메서드 A의 경우는 함수를 두번째 부를 타이밍 전에 실행되지만 메서드 B의 경우는 A 함수의 두번째 호출로 파생된 작업이 모두 끝난 경우에 실행된다
- 8퀸 문제의 해설처럼 함수를 호출하고 함수가 종료된 후에 함수 호출 이후에 정의되어 있는 메서드가 실행된다 생각하면된다
- 1 작업처럼 함수가 호출되고 호출되며 동시에 수행되는 A 메서드는 실행되지만 메서드 B는 직전에 호출된 함수를 우선으로 하기에 실행되지 않고 스택에 쌓인다
- 함수 호출이 모두 종료된 이후에 2 작업이 시작
- 재귀는 stack 구조이기에 늦게들어간 작업부터 실행
- 참고 문제 : https://velog.io/@sung-ik-je/%EB%B0%B1%EC%A4%80-17478
재귀 알고리즘 분석
- 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라 표현
- 복잡한 구조를 가졌으며 좀 더 전략적으로 분석이 필요하며 두 가지 방법 이용
- 하향식(top down) 분석
- 가장 위쪽에 위치한 상자의 메서드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법
- 같은 메서드의 호출이 여러 개일 수도 있다
- 때문에 반드시 효율적이라고 말할 수 있는 것은 아님
- 알고리즘에 시작~끝 순으로 조사
- 상향식(bottom up) 분석
- 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법
- 알고리즘의 끝~시작 순으로 조사
- 비재귀적 표현
- 재귀가 2개 이상인 경우
- 꼬리 재귀
- 마지막 재귀 호출
- 재귀
- 처음 재귀 호출
문제
하노이의 탑(Towers of Hanoi)
- 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘
- 작은 문제로 세분화시켜 해결
- 3개지의 원판을 옮기는 것을 바탕으로 재귀적 알고리즘으로 해결
- 재귀적 알고리즘에서 흐름을 잘 파악해야된다
- 어떤 경우의 수부터 거꾸로 시작인지를 잘 파악 필요
8퀸 문제(8-Queen problem)
- 가지 뻗기
- 분기 한정법(branching and bounding method)
- 가지 뻗기 + 한정(bounding) 조작
- 한정(bounding) 조작
- 가지 뻗기에서 각 행에 퀸을 1개만 배치하기 위해 flag 함수 이용
- 퀸 유무 체크해 가지 뻗기에서 특정 행에 퀸 위치한 경우를 제외한 작업 반복
- 코드 : flag[j] = flase;
- 재귀 호출한 set(i+1) 메서드 실행이 끝나면 j행에 퀸이 제거 되므로 false처리
- 8퀸 문제가 아니라 8룩(Rook) 문제를 풀었다라고 말할 수 있다
- 퀸은 대각선으로도 이동가능하기 때문
- 어떤 대각선 방향으로도 이동해도 퀸이 1개인 한정 조작을 추가해줘야 한다
- 8퀸 문제
- 가지 뻗기 + 한정 조작1 + 한정 조작2
- 한정 조작으로 퀸의 영향력이 행사하는 부분들을 억제하는 것
- 한정 조작 1 : 퀸의 좌,우 운동 방지
- 한정 조작 2 : 퀸의 대각선 운동 방지
- 상,하 운동의 경우 가지 뻗기에서 미리 제외
피보나치 수열
유클리드 호제법(Euclidean method of mutual division)
- 두 정수의 최대공약수(gratest common divisor)를 재귀적으로 구하는 방법
- 두 정수를 직사각형의 각 변이라 예를 들어 설명
- 정사각형으로 나눠 가며 계산(=큰 수 에서 작은 수를 나눠 나머지 값만 필요)
- 계속해서 나눠가며 나오는 두 가지 정수에서 큰 값을 작은 값으로 나누었을 때 나누어 떨어지는 가장 작은 값이 최대 공약수
- 나눠 떨어질 때 까지(나머지가 0일 때 까지) 계산 과정 반복
- 큰 수에서 작은 수를 나눠가며 나머지가 존재하지 않을 때 까지 반복하며, 존재하지 않을 때 직전에 수가 최대 공약수
Divide(or Decrease) and conquer
- 원래 문제를 더 작은 문제로 쪼개어서 혹은 축소하여, 작은 문제들을 해결함으로써 원래 문제를 해결
- 재귀적 기법 또는 반복문 활용
- 반복문은 시작과 끝, 스텝 구간 등을 처음 정의하며 시스템이 순차적으로 돌아간다고 생각하면 되고 재귀의 경우 시작과 끝 모두 함수 내에 정의되어 있으면서 반복문처럼 처음부터 끝까지 순차적이라기 보다 프로그램이 돌아가는 과정이 순차적이다.
- 재귀 함수 내에 정의되어 있는 끝이 나는 조건의 코드를 base case라고 한다
