[js] 재귀호출을 반복문으로 바꾸기

개요

알고리즘 작성 시 여러 단계의 중첩이 반복적인 로직으로 진행되는 경우 재귀호출을 쓰게 되는 건 사고의 흐름 상 자연스러운 것입니다. 하지만 언어의 스택오버플로우 제약에 따라 트렘폴린 등의 방법을 같이 동원해야하죠. 사실 꼬리물기 최적화를 지원하지 않는 언어에서 재귀를 고수하며 작성할 이유는 전혀 없습니다. 되도록이면 반복문으로 고쳐야합니다. 왜냐면 이 문제는 단순히 속도 차라고 보기엔

1. 성능 측정을 위한 십만번, 백만번 반복하지 않아도
2. 실용적인 몇 십번, 몇 백번 단위에서도 확연하게 성능 차이가 많이 나기 때문입니다.

하지만 이를 실제 복잡한 알고리즘 별로 적용하려면 깊은 이해가 필요하고 개인적인 역량에 따라 번역이 되고 안되고 하는 문제가 있습니다. 이번 포스팅에는 이를 좀 더 연구하여 보다 쉽게 재귀호출과 반복문을 번역하도록 안내하려 합니다.

연산식의 스택

알골60의 자손들인 언어 대부분은 좌에서 우로 순차적인 해석을 기본으로 하고 있습니다. 따라서 연산자 우선 순위가 동일하다면 좌에서 우로 순차적인 실행을 한다고 할 수 있겠죠.

//좌에서 우로
let a;
a = 1 + 2 + 3 + 4;

//결국 차근차근 순차적으로 실행됨
let a;
a = 1 + 2;
a = a + 3;
a = a + 4;

여기서 알 수 있는 점은 연산식에 연산자가 여러 개 있는 경우 암묵적으로 스택이 형성된다는 점입니다. 이는 괄호를 고려해보면 굉장히 명확합니다.

let a;
a = 1 + (2 + 3);

위 식에서 최종 결과에 도달하려면 우선 괄호 안이 해소되어야 합니다. 따라서 (2 + 3) 의 결과인 5를 ‘어딘가’ 저장한 뒤 반환하여 원래 수식을 1 + 5 로 만들어서 최종 결과인 6이 됩니다.
따라서 6이 나오려면

1. 1 + (괄호) 라는 최초 식을 기억하고 있는 상태에서
2. 별도의 메모리에서 (2 + 3)을 처리해야 한다는 사실을 알 수 있습니다.

간단히 말하자면 연산식은 스택을 형성한다는 것입니다. 이 개념을 이용하면 연산식의 모양에 따라 얼마나 많은 스택이 유지되어야 하는지 알 수 있습니다.

연산식 스택의 깊이와 반환포인트

a = 5 + (3 + (1 + 2));

위 식의 경우

1. 스택0 – 전체 수식 = 5 + 괄호
2. 스택1 – 첫째 괄호 = (3 + 괄호)
3. 스택2 – 둘째 괄호 = (1 + 2)

총 3단계의 스택이 있어야만 수식을 해결할 수 있습니다. 중첩된 괄호의 수가 결국 스택의 깊이가 되는 것이죠. 이와는 다르게 병렬 관계의 괄호는 스택의 깊이를 더할 필요는 없습니다.

a = (1 + 2) + (3 + 4);

위의 식은

1. 스택0 = 괄호 + 괄호
2. 스택1 = (1 + 2)
3. 스택0 = 3 + 괄호, 스택0에 반환되어 스택1은 해제
4. 스택1 = (3 + 4)
5. 스택0 = 3 + 7, 스택0에 반환되어 스택1은 해제
6. 스택0 = 10

위와 같이 병렬 단계는 순차적으로 부모 스택에 반환되고 본인 스택을 해지하므로 스택의 깊이를 쌓지 않아 스택이 깊어지는 것을 방지할 수 있습니다(물론 이는 언어의 구현 방법에 따라 달라질 수 있습니다)
이렇듯 연산식의 각 단계가 해소되고 원래 수식에 대체되는 원리를 생각해보면

각 스택 단계에서 해소된 값은 원래 스택에 돌아갈 포인트를 알고 있다

고 생각해볼 수 있습니다. 즉 아래와 같은 관점을 갖을 수 있는 거죠.

a = (1 + 2) + (3 + 4); //스택0상태
a = [스택1(1+2)이 해소되고 돌아올 포인트] + [스택1(3+4)이 해소되고 돌아올 포인트]

다른 면으로는 연산식의 각 스택단계가 진행될 때

1. 한 단계 깊은 스택을 만드는 경우,
2. 그 만들어진 스택의 결과가 돌아올 원래 스택의 포인트도 같이 정해준다

라고 할 수 있습니다.
즉 원래 수식이 (1 + 2) 라는 스택을 생성할 때는 이미 (1 + 2)의 결과가 어디로 들어와야 하는 지도 미리 정해두었다는 것입니다. 이러한 원리로

1. (1 + 2)결과는 앞 쪽에,
2. (3 + 4)결과는 뒷 쪽에 지정된 포인트로 들어와
3. 원래 수식은 3 + 7로 변화하여 최종 결과 10이 도출되는 것입니다.

함수 호출과 연산식 스택의 상호작용

결국 연산식은 스택을 갖게 되므로 함수 호출과 맞물리면 연산식의 스택과 함수 호출의 스택마저 감당하는 형태가 됩니다.

a = 1 + sum(2, 3, 4);

위의 식은 다음의 과정으로 해소될 것입니다.

1. 스택0 = 1 + 함수호출결과
2. 함수 호출스택0 sum(2, 3, 4)의 해소
3. 스택0 최종 해소

즉 연산식이 함수 호출로 인한 스택을 대기하는 형태가 되어 연산식 자체는 스택을 1단계만 필요하지만 사실 상 함수 호출스택을 끌어안아 2단계 스택이나 마찬가지 상태가 됩니다.
따라서 함수 호출이 연산식에 포함되는 경우는 연산식에 값만 있는 경우보다 더 복잡한 양상을 띄게 됩니다.

위의 관점은 연산식이 주가 되고 그 안에 부속으로 함수 호출이 들어있는 경우입니다만 그 반대로 보면 어떨까요?
즉 함수 호출 내부에 연산식이 결부되는 경우입니다.

const sum = (...arg)=>{
  switch(arg.length){
  case 0: return 0;
  case 1: return arg[0];
  case 2: return arg[0] + arg[1];
  default: return arg[0] + sum(...arg.slice(1));
  }
};

sum 함수는 전형적인 재귀함수로 인자에 따라 다르게 반응하는데 2개까지는 직접 처리하지만 3개부터는 재귀를 통해 문제를 떠넘기는 방식으로 처리됩니다.
이 경우 반환 값에 연산식이 들어있는 인자가 3개 이상일 때의 default:를 보면 arg[0] + sum(..) 사이에 덧셈 연산식이 들어가 있습니다.
이는 반대로 말하자면

1. 덧셈연산식 스택이 해소되려면 sum(…arg.slice(1)) 호출 스택이 해소되어야 하고
2. 덧셈연산식 해소되기 전까지는 sum함수가 반환될 수 없다 라고 할 수 있습니다.

앞 서 연산식은 스택을 추가할 때 반환포인트도 같이 설정한다고 했는데, 이는 함수 호출이 연산식에 들어올 때도 마찬가지입니다. 위의 수식을 다시 살펴보면

a = 1 + sum(2, 3, 4);

a = 1 + [sum함수 호출의 결과가 반환될 곳];

이라고 볼 수 있을 것입니다. 즉 함수의 호출 결과가 돌아올 포인트를 함수 호출 시에 넘겨준 셈이죠. 함수는 자신의 return이 어디로 들어가야 하는지 아는 상태에서 호출된 것입니다.

일반적인 꼬리물기 최적화로 바꾸기

보통 꼬리물기 최적화는 굉장히 간단하게 설명할 수 있습니다.

return문에 함수호출이 포함된 연산식을 제거한다

이를 달성하려면 위의 함수를 살짝 고쳐야 합니다. 기존의 함수를 다시 살펴보죠.

const sum = (...arg)=>{
  switch(arg.length){

  //ok! 단순값
  case 0: return 0; 

  //ok! 단순값
  case 1: return arg[0]; 

  //ok! 단순값 연산식
  case 2: return arg[0] + arg[1]; 

  //no! 함수호출을 포함한 연산식!!!!
  default: return arg[0] + sum(...arg.slice(1));
  }
};

문제는 마지막이네요. 나머지는 위의 방법에 어긋나지 않으므로 문제 없습니다. 마지막을 다음과 같이 고치면 될 것입니다.

const sum = (...arg)=>{
  switch(arg.length){
  case 0: return 0;
  case 1: return arg[0];
  case 2: return arg[0] + arg[1];

  //ok! 연산식 없는 함수 호출로 변환
  default: return sum(...[arg[0] + arg[1], ...arg.slice(2)]);
  }
};

그렇습니다. 조건은 “함수 호출을 포함한 연산식이 없게 하라” 는 것이지만, 달성 방법은 일반적으로 “연산식이 없는 함수호출”입니다.
이렇게 하면 연산식 때문에 생기는 스택은 제거가 됩니다. 하지만 위의 내용으로는 약간 의문이 들죠.

1. 원래 수식인 “1 + sum(2, 3, 4)” 에서 sum함수의 결과는 “1 + 여기”에 들어온다.
2. sum(2, 3, 4) 내부에서 “return sum(5, 4)” 로 처리되고 이는 “return 여기”에 들어온다.
3. 결국 sum(5, 4)가 먼저 return포인트에 반환되고 나서 sum(2, 3, 4)가 연산식의 반환포인트에 들어오는 것이 아닌가!

그렇습니다. 2단계를 거쳐 연산식의 반환포인트에 들어오는 것이죠. 그런데 말이죠..
위의 1,2,3을 자세히 보면 다음과 같은 전개가 가능합니다.

1. 원래 수식인 “1 + sum(2, 3, 4)” 에서 sum함수의 결과는 “1 + 여기”에 들어온다…여긴 같습니다.
2. sum(2, 3, 4) 은 연산식에 반환될 포인트를 알고 있다..그렇죠 반환값을 연산식에 돌려줘야하니까.
3. 내부에서 “return sum(5, 4)” 로 처리되고 이는 “return 여기”에 들어온다…이걸 좀 바꿔보는 겁니다.
4. sum(5, 4)에게 자기가 알고 있던 연산식의 반환포인트를 걍 알려주면 어떨까?

즉 2단계로 호출되던 sum(5,4)에게 sum(2,3,4)의 return문에 있는 반환포인트가 아니라 아예 sum(2,3,4)가 알고 있던 “1 + 여기”의 반환포인트를 줘버리는 겁니다.
그러면 sum(5,4)는 더 이상 return에게 반환하려 하지 않고 곧장 “1 + 여기”에 반환하려고 하겠죠.

이를 이용하면 sum(2,3,4)는 sum(5,4)를 호출하는 시점에서 곧장 자신의 스택을 해제해버리고 병렬적으로 sum(5,4)가 스택을 이어받게 할 수 있습니다.
바로 이것이 꼬리물기 최적화의 원리인 셈입니다. 또한 반드시 언어가 지원해야만 실현할 수 있는 기술이기도 하죠.

지금까지의 복잡한 설명을 그림으로 표현하면 다음과 같을 것입니다.

위의 이미지에서
1. 가장 좌측 스택단계를 보면 3단계가 필요하다는 것을 알 수 있습니다.
2. 반투명 파란박스가 각 스택이 반환할 때 어디로 반환되는지에 대한 반환포인트라 할 수 있죠.

만약 꼬리물기 최적화를 지원한다면 다음과 같이 처리될 것입니다.

1. sum(2,3,4)는 sum(5,4)를 호출하는 시점에 자신의 스택을 해지하므로 다시 함수호출 스택이 아무것도 없는 상태가 됩니다.
2. 따라서 sum(5,4)는 다시 함수호출 스택0에서 시작될 것입니다.
3. 또한 sum(5,4)는 더이상 sum(2,3,4)의 포인트에 반환하지 않고 곧장 이어받은 연산식에게 반환하게 될 것입니다.

같은 원리를 이용한 제어문 치환

결국 꼬리물기 최적화를 이용하면 매 단계 마다의 스택을 제거하고 새로운 함수 호출에 따른 스택 하나만 유지할 수 있게 됩니다.
이를 전문적인 용어로 스택클리어라고 합니다. 스택클리어는 언어의 구조 상 보통 두 가지로 구현되는데, 위에서 봤던 꼬리물기 최적화와 제어문에 있는 for, while 등의 루프문입니다.

반복문은 매 반복 시점마다 처리된 내용을 쌓지 않고 곧장 스택을 해지하므로 무한루프를 돌 수 있게 해줍니다. 대신 남겨야 할 것은 변수에 남기는 방식을 사용합니다. 따라서 재귀호출을 제어문을 바꿀 때는 다음의 센스가 필요합니다.

1. 재귀에서는 반환포인트를 자동으로 처리하지만 반복문에서는 직접 스택구조를 작성해야한다.
2. 재귀에서는 인자가 자동선언 되므로 변수를 직접적으로 제어할 필요가 현저히 적어지지만, 반복문에서는 필요한 만큼의 변수를 선언하고 매 반복시마다 초기화해야한다.

위의 두 가지 센스를 갖고 sum함수를 반복문으로 개편해보죠.

const sum = (...arg)=>{
  const stack = [];
  let current = arg, result = 0;

  do{
    //current를 이용하여 처리한다.
  }while(current = stack.pop());

  return result;
};

기본적인 틀을 보면
1. 재귀함수가 처리해주던 스택구조가 없으므로 직접 배열로 스택구조를 만들고 현재 스택을 처리하다가 스택이 더이상 없으면 종료되는 형태를 생각해볼 수 있습니다.
2. 또한 return이라는 개념이 없으므로 결과를 수집할 result변수가 필요하고 최종적으로 이것을 반환하게 됩니다.

바로 위에서 언급한 2가지 센스에 해당되는 구조라 할 수 있습니다. 속을 채우는 것은 기존 로직과 거의 동일합니다만 재귀 호출 부분을 스택생성으로 대체하면 됩니다.

const sum = (...arg)=>{
  const stack = [];
  let current = arg, result = 0;

  do{
    //기존로직과 동일하나 return대신 result에 결과를 병합한다.
    switch(current.length){
    case 0: result += 0; break;
    case 1: result += current[0]; break;
    case 2: result += current[0] + current[1]; break;

    //기존 재귀함수호출 대신 스택에 넣어서 반복문에 맡긴다.
    default: stack.push([current[0] + current[1], ...current.slice(2)]);
    }
  }while(current = stack.pop());

  return result;
};

기존 재귀함수를 다시 볼까요?

const sum = (...arg)=>{
  switch(arg.length){
  case 0: return 0;
  case 1: return arg[0];
  case 2: return arg[0] + arg[1];
  default: return sum(...[arg[0] + arg[1], ...arg.slice(2)]);
  }
};

do..while문 안을 보면 거의 동일하다는 것을 알 수 있습니다. 즉 반대로 말하자면 다음과 같은 것을 찾아낼 수 있죠.

1. 재귀호출을 반복문으로 고치려면 이미 재귀함수가 꼬리물기 최적화 형태로 되어있어야 한다.
2. 꼬리물기 최적화가 끝나있는 함수는 return을 결과 변수에 취합하는 것으로
3. 재귀호출을 스택에 넣어주는 것으로 갈음하면 간단히 번역될 수 있다.

결론

연산식의 처리와 함수 호출에는 스택을 생성한다는 공통점이 있습니다. 하지만 미묘한 차이점이 있고, 무엇보다 그 둘의 상호 작용으로 복잡한 양상을 만들어 냅니다.
이 부분에 대한 섬세한 고찰을 통해 언어 상의 스택 구조에 대한 이해를 넓힐 수 있으며 궁극적으로 글의 제목대로 재귀호출과 반복문 사이를 자유롭게 바꿀 수 있는 능력을 키울 수 있습니다.
해서 이 번 포스팅에서는 연산식, 함수의 호출, 재귀호출과 꼬리물기 최적화, 반복문에서의 스택구조 등을 순서대로 살펴봤습니다.

아시다시피 대부분의 브라우저는 js에 대해 여전히 꼬리물기 최적화를 지원하지 않고 있습니다. 특히 pc용은 그나마 상황 개선의 여지가 보이기도 하지만 안드로이드 레거시가 사라질 타이밍을 생각하면 당분간 꼬리물기 최적화를 전재로 하는 알고리즘은 무리라고 생각됩니다(안드로이드가 새로운 IE다!)