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

코드출처: Doit! 자료구와 함께 배우는 알고리즘 입문 (자바 편)의 174~177페이지

다음의 간단한 재귀함수를 비재귀적으로 표현해보자.
이 활동은 재귀함수의 동작 과정의 이해를 돕는다.

이번 포스팅의 학습 목적은 "재귀함수의 동작 원리를 깔끔하게 이해하여, 같은 동작을 비재귀적으로 표현할 줄 알기"이다.

---

1. 다음의 재귀함수를 보자.

static void recur(int n) { 
  if (n>0) { 
    recure(n-1); 
    System.out.println(n); 
    recur(n-2); 
  } 
}

두 번의 재귀호출이 존재하는 메서드 recur이다.

동작 설명:
메서드의 인자로 어떤 양수 n이 들어오면,
- recur(n-1) 동작이 완전히 수행된 후
- n을 출력하고
- recur(n-2) 동작이 완전히 수행된다.

이 메서드의 가장 마지막에 있는 재귀(꼬리재귀)인 recur(n-2)는 쉽게 비재귀적 표현으로 바꿀 수 있다. 왜냐하면, 앞선 재귀호출 recur(n-1)과 n의 출력을 '모두 완수한 후' 수행하는 마지막 재귀이기 때문이다. 단순히 인자 n-2에 대해서 다시 메서드의 맨 처음으로 돌아가서 해당 메서드의 모든 동작을 수행하게 하면 된다. (그런 동작이 즉 재귀의 동작이기 때문이다.)

2. 꼬리재귀(recur(n-2))를 제거한 모습

static void recur(int n) { 
  while (n>0) { 
    recur(n-1); 
    System.out.println(n) 
    n = n-2; 
  } 
} 

그냥 마지막에 n을 n-2로 업데이트하고 
메서드의 처음으로 돌아가서 
업데이트된 n에 대해 같은 과정을 반복해주면 된다.

이렇게 마지막의 재귀호출은 아주 쉽게 비재귀적으로 구현해볼 수 있었다. 그러면 이제 맨 앞에 끼어있는 재귀인 recur(n-2)을 비재귀적으로 표현하는 방법을 고민해보자.

고민해야 할 내용은 다음과 같다.

- 재귀호출 recur이니까 n을 n-1로 업데이트 한 후 메서드의 처음으로 되돌아간다면?
- 만약 그렇다면 recur(n-1)을 완전히 수행한 뒤 돌아왔을 때 문제가 생긴다. 왜냐하면 원래의 n이 사라져서 System.out.println(n)이 난감해진다.
- 즉, recur(n-1)을 처리하고 다시 돌아와서 n을 출력해줘야 한다. 이 말은 즉 n값을 잠시 '저장해두어야'한다.

그렇다면,
n을 잠시 저장해두기 위해 어떤 자료구조가 적절할까? 스택을 이용하면 된다.

스택은 후입선출의 자료구조이기 때문에 위 재귀함수의 동작을 고려할 때 n을 저장해두기에 아주 적절한 선택지이다. stack에 n을 저장해두고나서 n을 갱신하고, 갱신된 n에 대한 모든 동작을 처리하고 돌아와서 저장해뒀던 n을 다시 꺼내쓰면 된다.
재귀함수는 연쇄적인 재귀호출을 수반하기 때문에 stack에 그때그때 처리해야 할 n이 점점 쌓여나간다. 재귀에 의해 stack에는 '더 먼저 처리해야 할' n값이 쌓이고, 재귀의 끝자락에 다다랐을 때 그제서야 가장 마지막에 쌓인 n을 처리한다. 그 n에 대하여 모든 동작을 완료했으면 그 이전의 n에 대해 처리하고, 처리하고 와서 그 이전에 쌓인 n을 처리하고.. 이러한 동작을 반복하면, 메서드의 최초 인자값 n에 대하여 모든 동작을 수행하게 된다.


그럼 이제 맨 앞의 recur(n-1)라는 재귀호출도 비재귀적으로 표현하여, 재귀함수 recur의 모든 재귀호출을 없애고 비재귀적으로 다시 표현해보자.

3. 모든 재귀호출을 제거하고 다시 비재귀적으로 구현

static void recur(int n) { 

  // 사용할 Stack 객체를 생성해주기 
  IntStack s = new IntStack(n); 
  
  while (true) { 
    if (n > 0) { 
      s.push(n); //일단 n을 스택에 저장해두고 
      n = n-1; 
      continue; //recur(n-1)을 돌리는 셈 
    } 
    // 이렇게 계속 n을 갱신하다가 
    // n이 음수가 되어 앞선 if문을 더 이상 돌릴 수 없다면, 
    // 즉, 연쇄적 재귀호출의 끝자락에 다다랐다면, 
    
    // 가장 최근에 저장해둔 n을 스택에서 꺼내서 
    // 해당 n에 대해 본래 메서드의 동작을 수행한다. 
    if (s.isEmpty() != true) { 
      n = s.pop(); 
      System.out.println(n); 
      n = n-2; continue; // 이 부분이 recur(n-2)에 해당 
    } 
    break; 
  } 
}

두번째 if문은, 앞선 재귀호출 recur(n-1)에 대한 연쇄적 재귀호출에 해당하는 모든 n을 저장해두고 나서 동작한다. 그 끝자락 n에 대한 동작을 모두 수행하고 두번째 재귀호출 recur(n-2)의 동작도 모두 수행하고 난 뒤에, 해당 n의 바로 이전 n으로 올라갈 수 있다. 한단계 위 n으로 올라가서 남은 동작을 모두 수행한 뒤 다시 한단계 위의 n으로 올라간다. 이를 반복하면서 초기 인자로 들어온 n에 대한 모든 동작도 수행하게 된다.