[C] 스택을 활용한 비재귀적 표현 및 메모이제이션을 통한 재귀함수 최적화

재귀 알고리즘 비재귀적으로 구현하기

#include <stdio.h>

void recur(int n){
  if(n>0){
    recur(n-1);
    printf("%d\n", n);
    recur(n-2);
  }
}

void main(){
  int x;
  printf("정수를 입력 : ");
  scanf("%d", &x);
  recur(x);
}

저번 포스트에서 다뤘던 이 재귀 알고리즘을 비재귀적으로 구현하려고 한다.

먼저 goto 문을 활용해 가장 아래에 있는 꼬리 재귀부터 제거해보겠다.

recur(n-2)를 풀어 설명하면 인자를 n-2로 전달하여 recur 함수를 호출한다는 뜻이다.

즉 n값을 n-2로 업데이트한 후 함수의 시작 지점으로 돌아가는것이라고 할 수 있다.

void recur(int n){
  Top :
  if(n>0){
    recur(n-1);
    printf("%d\n", n);
    n = n-2;
    goto Top;
  }
}

이제 남은 위쪽을 살펴보면 recur(n-1)를 수행한 후 n값을 출력해야한다.

하지만 꼬리 재귀를 제거할때처럼 n값을 n-1로 업데이트하고 함수의 시작으로만 돌아간다면 recur(n-1) 부분의 실행이 종료되고도 재귀가 반복되는 동안 n값이 달라져 의도한 값을 출력할 수 없을 것이다.

이를 해결하기 위해 우리는 n값을 잠시 저장해놓고 저장했던 n값을 꺼낼 것이다.

이때 후입선출 구조로 가장 최근에 저장된 값을 꺼내며 프로그램이 실행될 것이기 때문에 이에 최적화된 자료구조인 스택을 사용할 것이다.

이전에 구현한 스택을 재사용하여 재귀 호출을 제거해보겠다.

#include <stdio.h>
#include <stdlib.h>

typedef struct{
  int max;
  int ptr;
  int *stk;
}IntStack;

int Initialize(IntStack *s, int max){
  s->ptr = 0;
  if((s->stk = calloc(max, sizeof(int))) == NULL){
    s->max = 0;
    return -1; //배열 생성 실패
  }
  s->max = max;
  return 0;
}

int Push(IntStack *s, int x){
  if(s->ptr >= s->max) return -1; //스택이 가득 찬 경우
  s->stk[s->ptr++] = x;
  return 0;
}

int Pop(IntStack *s, int *x){
  if(s->ptr <= 0) return -1; //스택이 비어있는 경우
  *x = s->stk[--s->ptr];
  return 0;
}

void Terminate(IntStack *s){
  if(s->stk != NULL) free(s->stk); //배열을 삭제
  s->max = s->ptr = 0;
}

int IsEmpty(const IntStack *s){
  return s->ptr <= 0; //참이면 1 반환 아닐 시 0 반환
}

void recur(int n){
  IntStack stk;
  Initialize(&stk, 100);
  Top :
  if(n>0){
    Push(&stk, n);
    n = n-1;
    goto Top;
  }
  if(IsEmpty(&stk) == 0){//위쪽의 재귀가 끝났지만 스택에 값이 남아있을시 후입선출 순서로 출력과 아래쪽 재귀 실행
    Pop(&stk, &n);
    printf("%d\n", n);
    n = n-2;
    goto Top;
  }
  Terminate(&stk);
}

void main(){
  int x;
  printf("정수를 입력 : ");
  scanf("%d", &x);
  recur(x);
}

즉 쉽게 말해 재귀로 구현했을때는 4를 실행하고 아래를 돌고나서 다시 4로 돌아왔지만, 비재귀적으로 구현했을때는 다시 돌아오지 않는다.

그러하여 그 값을 스택에 저장한 다음 실행이 끝나고 난 후 스택에 요소가 남아있을 때 가장 최근에 넣은 요소로 아래의 재귀를 실행함으로써 비재귀적으로 구현할 수 있는 것이다.

이때 가장 마지막 재귀도 똑같은 방법으로 구현했지만 추가적인 작업이 필요하지 않았던 이유는, 마지막 코드이기에 재귀를 실행하고 다시 n값으로 돌아와 해야할 작업이 없기 때문이다.

메모이제이션(memorization) 활용하기

recur 함수를 실행하는 과정에서 같은 연산을 여러 번 반복해서 수행한다.

같은 결과의 연산을 반복하는 프로그램은 비효율적이기에, 메모화 또는 메모 기법이라고 불리는 메모이제이션을 사용할 것이다.

메모이제이션은 어떤 문제에 대한 해답을 메모해두고 같은 문제에 대한 호출에 대해 메모해 둔 내용을 반환하는 방법이다.

#include <stdio.h>
#include <string.h>

static char memo[128][1024];

void recur(int n){
  if(memo[n+1][0] != '\0'){
    printf("%s", memo[n+1]);
  }else{
    if(n>0){
      recur(n-1);
      printf("%d\n", n);
      recur(n-2);
      sprintf(memo[n+1], "%s%d\n%s", memo[n], n, memo[n-1]);
    }else{
      strcpy(memo[n+1], "");
    }
  }

}

void main(){
  int x;
  printf("정수를 입력 : ");
  scanf("%d", &x);
  recur(x);
}

메모이제이션으로 연산 횟수가 얼마나 줄었는지 확인해보기 위해 연산시에 recur(n)을 출력하도록 하여 비교해보았다.

기존 코드 실행 결과

정수를 입력 : 5
recur(5)recur(4)recur(3)recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)3
recur(1)recur(0)1
recur(-1)4
recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)5
recur(3)recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)3
recur(1)recur(0)1
recur(-1)

---------------------------
메모이제이션 후 실행 결과

정수를 입력 : 5
recur(5)recur(4)recur(3)recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)3
recur(1)1
4
recur(2)1
2
5
recur(3)1
2
3
1

비교해본 결과 함수 호출 횟수가 25번에서 11번으로 줄어 반복되는 연산을 14회나 줄여 더욱 효율적인 코드를 짤 수 있었다.

이렇게 스택을 통해 재귀함수를 비재귀적으로 표현해보고 메모리제이션을 활용해 최적화까지 해보았다.

다음 포스트에서는 재귀를 이용한 하노이 탑에 대해 알아보자.