데이터 구조와 알고리즘 2장

재귀와 백트래킹

재귀: 자기 자신을 호출하는 함수를 재귀적이라고 부른다.
      *재귀가 확실히 종료되게 해야 한다.

 - 재귀 함수의 형식
 재귀 함수는 하위 작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다. 어느 단계에 이르러서는, 자기 자신을 호출하지 않고도 수행할 수 있는 하위 작업을 수행한다. 이렇게 함수가 재귀 호출하지 않는 것을 기본 경우라고 하고, 함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우라고 한다.

if (기본 경우인지 테스트)
   return 기본 경우 값
else if (또다른 기본 경우 테스트)
     return 다른 기본 경우 값
//재귀 경우
else
    return (어떤 작업) 그런 다음 (재귀 호출)

ex) 팩토리얼 함수
//양의 정수의 팩토리얼을 계산한다.
int Fact(int n) {
   // 기본 경우: 0이나 1의 팩토리얼은 1이다
    if (n == 1)
       return 1;
    else if (n == 0)
         return 1;
// 재귀 경우: (n - 1) 팩토리얼에 n을 곱한다.
    else
         return n*Fact(n - 1);
}


 - 재귀와 메모리(시각화)
재귀 호출될 때마다 메서드의 복사본이 메모리에 만들어진다. 메서드가 종료할 때, 리턴하는 메서드의 복사본은 매모리에서 삭제된다.

ex) n = 4일 때, 팩토리얼 함수 표현

 재귀
기본 경우에 도달하면 종료한다.
각 재귀 호출은 메모리에 부가 공간을 필요로 한다.
무한 재귀에 들어가게 되면 메모리 용량을 초과해서 스택 오버플로우를 초래하게 된다.
어떤 문제들의 해답은 재귀적인 수식으로 만들기 쉽다.

 반복
조건이 거짓이 될 때 종료한다.
각 반복이 부가 공간을 필요로 하지 않는다.
무한 루프는 추가 메모리가 필요하지 않으므로 무한히 반복된다.
반복적 해법은 재귀적 해법에 비해 간단하지 않을 때가 있다.


 - 백트래킹
백트래킹은 분할 정복을 이용한 완전 검색 기법이다,

어떤 경우에는 문제를 푸는 최선의 알고리즘이 모든 경우의 수를 다 살펴보는 것이다.
이 방법은 항상 느리지만 도움이 될 수 있는 표준적인 도구들이 있다.
ex) 도구: 기본 오브젝트를 생성하는 알고리즘들
         이진 문자열(n-bit 문자열에 대해 2^n 확률)
         치환(n!), 조합(n!/r!*(n-r)!)
         일반화된 문자열(길이가 n인 k-ary 문자열은 k^n 확률)
백트래킹은 가지치기를 이용해 완전 검색을 빠르게 한다.