1. 재귀적 관계 (재귀적 문제)의 응용 例)
ㅇ 수열의 점화식 : 수열의 (n)항과 (n-1)항 간의 관계식
- (점화식 : 특정 항을 그보다 작은 항들에 의한 관계식으로 표현한 식)
ㅇ 피보나치 수열 : (직전 2개 항의 합으로 정의됨)
- fibonacci(0) = 0; fibonacci(1) = 1; fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);
ㅇ 팩토리얼 : (현재 항 및 직전 항의 곱으로 정의됨)
- factorial(1) = 1; result = factorial(n) * factorial(n-1);
ㅇ 이항 계수 : (각 계수 마다, 현재 항,직전 항,... 등의 합으로 정의됨) ☞ 이항계수,조합 참조
- [# \binom{n}{k} = C(n,k) = {_nC_k} = \frac{P(n,k)}{P(k,k)} = \frac{n!}{(n-k)!k!}
= \frac{n(n-1)\cdots(n-k+1)}{k!} #]
ㅇ 하노이 탑 : (재귀 호출을 이용해서 풀 수 있는, 오래된 가장 유명한 예제)
- 점화식 : T(n) = 2 x T(n-1) + 1, 일반항 : Tn = 2n -1
ㅇ 재귀적 알고리즘 : 병합 정렬, 퀵 정렬, 이진 탐색, DFS, 백트래킹 등
2. 재귀 호출 / 재귀 함수 / 순환 함수 / 재귀 서브프로그램 이란?
ㅇ 호출된 함수가 다시 자기자신을 호출하는 것
- 자기 자신을 이용하여 정의시켜 놓고,
- 반복적으로 스스로를 호출/사용하는 함수 (Recursive Function)
ㅇ 용도
- 통상, 문제 내 작은 형태의 문제가 연이어 포함된 내포구조의 프로그래밍에 적합
. 자기 자신을 다시 호출하며 문제를 푸는 방법을 씀
- 마치 루프처럼 어떤 일을 반복적으로 수행하는데에 유리함
- 트리 및 연결 리스트와 같은 컴퓨터 자료구조에 유용
ㅇ 구현
- 재귀 호출의 복귀를 위해, 주로, 스택 자료구조를 활용하여 복귀함
3. 재귀 함수의 요건 및 프로그래밍시 고려사항
ㅇ 필수 요건 둘(2)
- ① 종료 조건 (stoppig condition), 기저 조건 (base case)
. 재귀적 호출에서 빠져나오는 탈출 조건
. 충분히 작아진 문제(종료 조건)에서, 직접 해결하고, 그 결과를 바로 윗선에 반환토록 함
- ② 재귀 호출 (recursive case)
. 각 단계 마다, 종료 조건에 접근하도록 그 자신을 재귀적으로 호출하게 됨
. 원래 문제 보다 작아진 부분 문제를 대상으로 함
ㅇ 프로그래밍시 고려사항 둘(2)
- 재귀를 멈추는(탈출시키는) 종료 조건을 정하고,
- 언제 어떤 매개변수로써, 재귀 호출할 것인지를 결정
4. 재귀 기법 및 반복 기법 간의 비교
ㅇ 재귀기법은 반복기법으로도 프로그래밍 구현이 가능 ☞ 반복문 참조
ㅇ 다만, 재귀(순환)은, 반복 보다 훨씬 명확하고 간결하게 표현 가능
ㅇ 결국, 프로그래밍 용이성 및 메모리 소요 크기로써 이 둘 (재귀/반복) 중에 선택 필요
5. 재귀 함수에 의한 구현 例)
ㅇ 팩토리얼 계산 例) (단, 0! = 1, 1! = 1)
function factorial(n) {
if (n <= 0)
return 1;
else
return n * factorial(n-1);
}
- n항의 최적 해법을 구하는 데, (n-1)항의 최적 해법을 사용하는, 최적의 하위 구조를 갖음
ㅇ 피보나치 수열 계산 例)
function fibonacci(n) {
if (n <= 2)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
- n항의 최적 해법을 구하는 데, (n-1)항,(n-2)항의 최적 해법을 사용하는,
최적의 하위 구조를 갖음
6. 재귀적 프로그래밍
ㅇ 재귀 함수를 사용하여 프로그래밍 하는 것
7. 재귀적 프로그래밍의 특징
ㅇ 프로그램을 직관적이고, 간결하게 작성 가능
ㅇ 특히, 내포 구조(nested)로 된 데이터를 다루기에 적합함
- 재귀 호출시, 함수 내 코드도 데이터 처럼 내포된 구조로써 포함되는,
- 일종의 추상 자료형 형태로도 볼 수 있음
ㅇ 최적의 하위 구조 (Optimal Substructure)를 갖음
- 크기가 더 작은 동일 유형의 하위 문제를 갖는 경우로써,
. 상위 문제와는 크기 만 작고 같은 유형을 갖는 하위 문제들을 포함하는 구조를 갖음
- 따라서, 하위 최적 해법을 사용해 상위 최적 해법을 구할 수 있음
ㅇ 재귀 호출은 루프(반복) 보다 다소 비효율적임
- 재귀 호출은 루프(반복)와 달리,
- 메모리에 함수 복사본을 반복적으로 만들기 때문에,
- 루프(반복) 보다 다소 느리고 더 많은 메모리가 필요
ㅇ 하위 문제의 반복 계산 (Overlapping Subproblems) 경우에는 느려짐
- 반복되는 (동일) 재귀 호출이 다수 발생하는 경우로써,
- 이로인해 실행 속도가 크게 늘어날 수 있음