재귀적 알고리즘

알고리즘 자신을 사용하여 정의된 알고리즘

비재귀적 알고리즘과 대비됨

작동원리

보류된 재귀호출을 위한 변수들에 관련된 저장/복구
→ 컴퓨터에 의해 자동적으로 수행

장단점

• 장점 : 복잡한 문제를 적은 양의 코드로 가독성 좋게 서술 가능
• 단점 : 컴퓨터 성능부담

재귀의 요소

• 재귀 케이스
• 베이스 케이스

Alg Factorial(n)
  input integer n
  output factorial of integer n
1. if(n==1)    {base case}
     return 1
2. else        {recursion case}
     return n*Factorial(n-1)

기본 규칙

아래 규칙을 따르지 않으면 재귀적으로 문제 해결 불가

• 베이스 케이스 : 항상 재귀없이 해결가능한 베이스 케이스를 가져야 한다.
• 진행 방향 : 재귀호출의 진행은 항상 베이스 케이스를 향해야 함
• 정상작동 가정 : 모든 재귀호출이 제대로 작동한다고 가정할 수 있어야 함
• 적절한 사용 : 꼭 필요한 곳에만 재귀를 사용해야 함 (성능저하 우려)

규칙을 따르지 못한 경우 아래 문제를 일으킬 수 있음

• 부정확한 결과 도출
• 미정지 (무한루프)
• 저장을 위한 기억장소 고갈

하노이 탑

• 하노이탑이란 https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi
• 큰 도움이 된 참고자료 : https://shoark7.github.io/programming/algorithm/tower-of-hanoi

아래 코드는 재귀적으로 하노이 탑을 해결하는 내용을 담고있다.
원판을 옮기는 것은 from말뚝, to말뚝의 출력으로 표현했다.

#include <stdio.h>

void move(int n, char from, char to){
  printf("n=%d\tmove from %c to %c\n", n, from, to);
}

void hanoi(int n, char from, char aux, char to){
  if(n==1){
    move(n, from, to);
  } else {
    hanoi(n-1, from, to, aux);
    move(n, from, to);
    hanoi(n-1, aux, from, to);
  }
}

int main(){
  int n;
  scanf("%d", &n);
  hanoi(n, 'A', 'B', 'C');
  return 0;
}

위 프로그램은 hanoi함수를 재귀적으로 호출한다.
이 함수의 재귀케이스를 살펴보면 아래의 절차를 관찰할 수 있다.
아래 파트 1~3 내용을 재귀적으로 호출하여 전체 문제를 해결한다.

파트1. from말뚝의 위쪽 n-1개를 aux말뚝으로 옮긴다.
파트2. from말뚝의 가장 아래(가장 큰) 1개를 to말뚝으로 옮긴다.
파트3. aux말뚝에 있는 n-1개 전부를 to 말뚝으로 옮긴다.

n=3인 경우 출력은 아래와 같다.

n=1 move from A to C	파트1
n=2 move from A to B	파트1
n=1 move from C to B 	파트1
n=3 move from A to C	---파트2
n=1 move from B to A	------파트3
n=2 move from B to C	------파트3
n=1 move from A to C	------파트3