재귀함수를 비재귀적으로 구현하기 예시 - 재귀함수 동작의 이해를 높이자

알고리즘 문제를 풀다보면 재귀함수를 비재귀적으로 구현해보라고 하는 문제가 자주 나온다.

 

얼마 전에도 재귀함수를 비재귀적으로 구현해보는 문제를 접했는데, 재귀함수의 동작 과정을 이해하고 받아들이는 큰 도움이 되었다: https://splendidlolli.tistory.com/343

재귀의 제거 | Stack에 잠시 저장해두기 | 재귀의 과정 이해 | 비재귀적 구현해보기

 

위 링크에서 풀었던 재귀함수 문제는, 메서드 내부에서 'recur(n-1)->print(n)->recur(n-2)'순서로 재귀호출과 n의 출력이 이루어졌다. 하지만 이번에 풀어볼 문제는 recur(n-1)->recur(n-2)->print(n)의 순서로 재귀호출하고 n을 출력하는 메서드를 비재귀적으로 구현하는 것이다. 

 

 

즉, 다음 메서드를 비재귀적으로 구현해볼 것이다

static void recur3(int n){
  if (n>0) {
    recur3(n-1);        //재귀호출1
    recur3(n-2);        //재귀호출2
    System.out.println(n);    //출력
  }
}

 

---

목차:

- 아이디어 구상

- 비재귀적구현1

- 비재귀적구현2

 

---

아이디어를 간단히 구상해보자

 

  일단 while(true)반복문 안에서 각종 조건문과 continue를 통해 재귀함수의 연쇄적 호출이 계속 될것이다. 재귀호출1이 일어난다는 것은 n을 n-1로 갱신하여 continue한다는 것, 그리고 재귀호출2가 일어난다는 것은 마찬가지로 n을 n-2로 갱신하여 continue한다는 것이다. 하지만 이렇게 갱신을 하기 전에는 반드시 본래 n을 스택에 차곡차곡 쌓아 본래의 n을 저장해두어야 한다. 그래야 해당 n에 대해 재귀호출1을 한 뒤 돌아와서 재귀호출2를 할 수 있고, println(n)도 정상적으로 수행할 수 있다. 

 

 

 

이런 재귀함수 문제를 풀 때 가장 먼저 떠올릴 수 있는 것은, 메서드의 초기 인자로 넣어 준 n을 스택에 차곡차곡 쌓아주는 것이다. 그 n에 대해 어떤 재귀호출, 이번 예시에서는 recur(n-1)이 일어나고, 연쇄적으로 n-1이 인자로 들어가는 동일한 메서드가 작동해나간다. n이 0 이하가 될 때까지 n을 차곡차곡 쌓아나간다. recur(4)를 예시로 들어보자. 

 

거창하게 그림까지 그렸지만 간단한 이야기다. 그냥 가장 먼저 연쇄적으로 일어나는 재귀호출1에 따라서, 각 호출의 인자에 해당하는 n을 기억해두어야 하므로 stack에 차곡차곡 쌓아두자는 말이다. 가장 나중에 들어가는 n에 대한 메서드를 가장 먼저 처리해야 하므로 stack의 구조가 알맞다. 후입선출의 자료구조이기 때문이다.

 

 

  어떠한 n의 시점에서 볼 때, 항상 재귀호출1인 recur(n-1)을 하고 돌아와서 recur(n-2)를 또 하고 돌아온 뒤 n을 출력하는 동작을 한다. 여기서 '다시 돌아온다'를 확실하게 처리해야 한다. 이게 무슨 말인지 설명하겠다. recur(n-1)을 하고 돌아와서 recur(n-2)를 시행하는 것은 큰 문제가 없을 것이다. 그런데 recur(n-2)를 처리하고 돌아올 때 어떻게 하면 recur(n-1)을 수행하지 않을 수 있을까? 이것을 고민하는 이유는 재귀호출 1,2 모두 while(true)문 내부에 있는 과정이기 때문에 continue를 만나면 항상 while문의 처음으로 돌아오게 되기 때문이다. 그래서 어떠한 n에 대하여 재귀호출2의 연쇄적 반응을 모두 마친 후에 다시 돌아와서 recur(n-1)을 하지 않도록 하는 장치를 만들어야 한다. 즉, 본래의 n에 대해 recur(n-1)까지 진행했는지 recur(n-2)까지 진행했는지 따져주는 장치가 필요하다. 그 장치를 통해 n을 출력할 차례인지 재귀호출2를 할 차례인지 판단이 된다. 

 

 

그래서 각 n에 대응하는 step스택을 만들어줄 것이다. step스택에는 n을 저장해둔 스택에 대응하는 step값을 입력해줄 것이다. n스택과 step스택의 대응은 각 스택의 인덱스 일치로 따져줄 것이다. 

 

설명은 이쯤 하고, 이제 코드와 함께 세부적으로 살펴보자. 

---

 

다음의 재귀함수를 

static void recur3(int n){
  if (n>0) {
    recur3(n-1);        //재귀호출1
    recur3(n-2);        //재귀호출2
    System.out.println(n);    //출력
  }
}

 

비재귀적으로 구현한 것은 다음과 같다

static void recur3(int n) {
  int[] nstk = new int[100];     //n을 쌓아둘 배열
  int[] sstk = new int[100];     //각 n의 step을 대응해줄 배열
  int ptr = -1;      //n과 step을 대응할 인덱스 ptr
  int step = 0;
  
  while (true) {
    if (n>0) {
      //일단 막바지까지 n을 쭉 스택에 쌓는다.
      ptr++;
      nstk[ptr] = n;
      sstk[ptr] = step;   //step을 부여한다
      
      if (step == 0)   //0스텝이면 recur(n-1) 돌리기 
        n = n - 1;
      else if (step == 1) {    //1스텝이면 recur(n-2)돌리기
        n = n - 2;      // n을 n-2값으로 갱신
        step = 0;       //갱신된 recur(n)를 돌리기 위해 step은 0으로 초기화
      }
      continue;
    }
    do {
      n = nstk[ptr];     //가장 최근의 n을 꺼내고 
      step = sstk[ptr] + 1;   // 위의 if문을 빠져나왔으니 최근 step을 꺼내 +1한다.
      ptr--;
      //왜 ptr-- 하는가?
      //1. step2인경우 print하고나서 다시 상위의 n으로 올라와야 한다. 
      //2. ptr<0과 관련있다. 처리할 n이 더이상 있는지 판단하기 위함.
      
      if ( step == 2 ) {   //recur(n-2)를 마치고 온 n이었다면,
        System.out.println(n);    //print한다.
        if (ptr < 0)
          return;
      }
   } while ( step == 2 );    
}

 

 

함께 달아놓은 주석으로 충분한 설명이 될 것 같다. 

 

step배열을 따로 두고, 인덱스를 나타내는 변수 ptr(포인터)를 통해 처리할 n과 그에 대응하는 step을 새겨두는 방식이 인상깊다. 

 

이 포스팅을 작성한 이유는 혼자 문제를 풀어보다가 이와 관련된 처리에서 막혔기 때문이다.

 

재귀호출1을 하고 돌아와서 또 재귀호출2를 해야 하는데, 재귀호출2를 하고 돌아와서 '재귀호출2를 하고 돌아온 상태다'를 판단해주는 장치를 어떻게 마련해야할지 고민을 많이 했었다. 결국 답안을 확인했는데, 따로 각 n에 대해 진행정도를 기록해두는 배열을 생성함으로써 해결하였다.

 

기억해둘만한 방법이라고 느낀다. 

 

---

또 다른 비재귀적 구현

  이번 코드는 뭐냐 하면, 내가 문제를 직접 해결하다가 실패한 코드에 살을 붇인 것이다. 문제 해결에 실패한 이유가 재귀호출의 진행 정도를 판단하는 장치를 못 넣어주어서이다. 추후에 답안을 보고 아이디어를 얻은 뒤에, 재귀호출이 어디까지 진행되었는지를 나타내는 단계를 또 다른 배열에다가 기록해두는 장치를 추가해보았다. 따라서 결국 호출의 단계를 n에 대응하여 기록해두는 방식은 동일하다.

 

그렇지만 내가 직접 고민하며 작성한 코드에 적절하게 장치를 추가해보았다는 점에서 의의가 있다. 

 

static void recur3(int n) {
  Stack<Integer> s = new Stack<Integer>();
  Stack<Integer> s2 = new Stack<Integer>();

  try {
    while(true) {
      if(n>0) { 
        s.push(n);
        s2.push(1);
        n = n-1; 
        continue;
      }
      if(s2.peek() == 1) {
        s2.pop(); 
        s2.push(2);
        n = s.peek()-2;
        continue;
      }
      if(s.isEmpty()!=true & s2.peek() == 2) {
        System.out.println(s.pop());
        s2.pop();
      }
    }
  } catch (java.util.EmptyStackException e) {
    return;
  }
}

내가 작성해서 그런지 더 잘 보인다.

그런데 잘 작성한 건지는 확신이 안간다. 어떻게 잘 작성했는지를 알아볼 수 있을까?