재귀란?
- 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우
- 재귀적 정의를 효과적으로 사용하면 프로그램을 간결하고 효율성 좋게 작성이 가능
- 재귀의 대표적 예시 : 팩토리얼
- 아래 사진은 함수 동작 과정을 그림으로 표현한 사진이다.
직접재귀와 간접재귀
- 자신과 똑같은 함수를 호출하는 방식을 직접재귀
- a() 함수가 b() 함수를 호출하고 b() 함수가 다시 a()함수를 호출하는 구조, 즉 다른 함수를 통해 자신과 똑같은 함수 호출
- 유클리드 호제법이란 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이며 여기서 호제법이라는 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.
- 파이썬에서는 최대 공약수를 구하는 표준라이브러리 math 모듈에서 gcd()함수를 제공해서 math.gcd(a,b)를 사용해 최대공약수를 구할 수 있고 두 인수가 모두 0이라면 0을 반환
재귀 알고리즘 분석
- 위 사진은 재귀함수와 이 함수를 호출하는 코드로 구성되어 있는데 재귀 호풀을 여러 번 실행하는 함수를 순수한 재귀라 하며 실제 동작은 복잡하다.
- 이를 분석하려면 2가지 방법이 존재하는데 하향식 분석과 상향식 분석이 존재한다.
- 아래 사진처럼 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석방법을 하향식 분석이라 한다.
1) recur(4)는 4를 출력하기 전에 recur(3)을 호출하고,
2) recur(3)은 3을 출력하기 전에 recur(2)를 호출한다.
3) recur(2)는 2를 출력하기 전에 recur(1)을 호출하고,
4) recur(1)은 1을 출력하기 전에 recur(0)과 recur(-1)을 출력하는데 이 둘은 실행되지 않으므로 1을 출력하고 위로 올라감
6) recur(2)에서 recur(1)은 이미 실행 됐고 recur(0)은 실행되지 않으므로 2출력해 1->2 순서가 되고 이 과정을 반복
- 상향식분석은 하향식 분석과 반대로 아래쪽부터 쌓아 올리며 분석하는 방법이다.
- 위 함수에서 재귀를 제거하려면 현재의 n값을 임시로 저장할 공간과, recur(n-1)의 처리를 완료하고 n값을 출력할 때 임시로 저장했던 n을 꺼내 그 값을 출력해야 하므로 후입선출이다. 따라서 우리는 스택을 이용해 재귀를 제거해야 할 수 있다.
x에 4를 대입했다면
4를 푸시 -> continue 문이 실행 -> while문 (스택에 4)
-> 3을 푸시 -> continue 문이 실행 -> while문 (스택에 43)
-> 2를 푸시 -> continue 문이 실행 -> while 문 (스택에432)
-> 1을 푸시 -> continue 문이 실행 -> while문 (스택에4321)
-> n이 0이 되어 두번 째 if문 실행 -> 1을 pop -> continue 문이 실행 -> while 문으로 돌아가기
-> n이 -1이 되어 두번 째 if문 실행 -> 2를 pop -> continue 문이 실행 -> while 문으로 돌아가기
-> n이 0이 되어 두번 째 if문 실행 -> 3을 pop -> continue 문이 실행 -> while 문으로 돌아가기
-> n이 1이 되어 첫번 째 if문 실행 -> 1을 푸시 -> continue 문이 실행 -> while문으로 돌아가기 과정을 반복하면 된다.
하노이의 탑
- 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제로 재귀 알고리즘 문제에 흔한 예시중 하나이다.
