자바스크립트 꼬리물기와 for에 관하여...

재귀 함수에 관하여 (&& unrolling recursion)

모든 프로그래밍 문제는 패턴을 찾으면 쉽게 해결할 수 있다.
우리는 패턴을 짜기에 가장 먼저 재귀 함수를 쉽게 떠올릴 수 있다. 그렇게에 주로 재귀 함수를 통해 문제를 해결하려고 한다.

1부터 num까지 더하는 재귀 함수

function sum(num){
  if (num == 1)
    return (1); 
  return (sum(num-1) + num);   
}

하지만, 재귀 함수들은 항상 stackoverflow의 위험 가능성이 있다.

우리는 고작 재귀 함수로 100000의 덧셈도 계산하지 못한다. 또한, 이런 코드들은 잠재적으로 버그를 일으킬 가능성이 높고 버그를 알기도 쉽지 않다.

꼬리물기 재귀 함수

C는 메모리를 모두 사용할 때까지 제한 없이 Call Stack을 쌓을 수 있지만, 일부 언어들은 그마저도 허용되지 않고 제한을 걸어서 일정량 이상 못 쌓이게 한다. 이에 수많은 선구자들은 언어 내에서 꼬리물기 함수를 생각해냈다.

메모리는 명령과 값으로 구성된다. 모든 프로그래밍은 메모리에서 명령을 cpu로 전달하여 값을 경신한다. 한 프로그램에서 모든 명령이 실행되면 프로그램은 종료된다. 프로그램이 시작되고 끝나기까지의 흐름을 Main Flow 라 하고, 함수의 분기된 흐름을 Sub Flow라고 하자. 우리는 Main Flow에서 Sub Flow를 호출했을 때 다시 Main Flow로 돌아오기 위해서 Sub Flow는 필연적으로 돌아올 주소를 가지고 있어야 함을 알 수 있다. 우리는 Sub Flow가 중복될 때마다 Stack을 쌓는다고 표현한다.

function sum(num){
  if (num == 1)
    return (1); 
  return (sum(num-1) + num);   
}

다음과 같은 함수의 return (sum(num-1) + num);에서 만약 return (sum(num-1))와 같이 돌아와서 해주어야 할 일이 없으면 우리는 이 Sub Flow에 저장된 돌아올 주소를 하위(Child) Sub Flow로 넘길 수 있다. 이 경우 우리는 Main Flow에 여러 Sub Flow가 겹쳐 있을 때 가장 하위의 Sub Flow에게 Main 함수로 돌아올 복귀 주소를 바로 넘길 수 있다.

즉, Stack이 쌓이지 않는 구조로 만들 수 있으며, 이를 꼬리물기가 가능한 함수로하고 한다. 실제, Javascript 표준은 꼬리물기 구현을 권장하지만, 사파리만 구현돼있고, Chrome은 향후에도 지원할 의사가 아직까지는 없다고 한다.

우리는 다음과 같이 꼬리물기 가능한 재귀 함수를 만들 수 있다.

function sum (v, acc) {
  if (v > 1)
    return (sum(v - 1, acc + v));
  return (acc + 1);
}

sum(10, 0)

NxN 정방 행렬에서 대각선을 기준으로 행렬의 원소를 뒤집는 알고리즘을 짜 보자.

NxN 정방 행렬에서 대각선을 기준으로 행렬의 원소를 뒤집는 알고리즘을 짜 보자.

처음부터 NxN을 생각하기엔 내 머리가 안 좋으니 3x3 작은 단위부터 생각해보자. 우리는 가장 먼저 2중 for문을 떠올릴 수 있다.

let arr = [[1,2,3], [5,6,7], [9,10,11]];

function reversePivot(pivot_matrix) {
  let tmp = [[],[],[]];
  for (let i = 0; i<3; i++) {
     for (let j = 0; j<3; j++) {
        tmp[j][i] = pivot_matrix[i][j];
     }
  }
  return (tmp);
}

for (let i = 0; i<3; i++)
  console.log(reversePivot(arr, 0)[i]);

하지만 N의 크기가 점점 늘어난다면.. 쉬운 문제야 패턴이 바로 보이지만, 문제가 어려워지면 패턴을 바로 찾아서 for문을 만들기가 힘들다.

프로그래밍에서 모든 문제는 패턴 찾기이다. 패턴을 가장 찾기 쉬운 방법이 재귀로 만드는 방법이다.
패턴을 찾아 for문 없이 재귀 함수로 짜 보자.

function reversePivot(pivot_matrix, i) {
  let tmp = pivot_matrix.map(v => v.slice());
  let tmp_num = pivot_matrix[i%3][Math.floor(i/3)];
  if (i == 8)
    return tmp;
  if (Math.floor(i/3) < i%3) {
    tmp[i%3][Math.floor(i/3)] = pivot_matrix[Math.floor(i/3)][i%3];
    tmp[Math.floor(i/3)][i%3] = tmp_num;
  }
  return reversePivot(tmp, i + 1);
}

모든 꼬리물기가 가능한 재귀 함수는 for문으로 기계적으로 치환이 가능하다. (수학적으로 증명됨)

let arr = [[1,2,3], [5,6,7], [9,10,11]];

let origin = arr.map(v => v.slice());
for (let i = 0; i < 8; i++) {
  let tmp = origin.map(v => v.slice());
  let tmp_num = origin[i%3][Math.floor(i/3)];
  if (Math.floor(i/3) < i%3) {
    tmp[i%3][Math.floor(i/3)] = origin[Math.floor(i/3)][i%3];
    tmp[Math.floor(i/3)][i%3] = tmp_num;
  }
  origin = tmp.map(v => v.slice());
}

for (let i = 0; i<3; i++)
  console.log(origin[i]);

위에 꼬리물기가 가능한 재귀 함수와 for문으로 짠 로직을 보고 어떤 부분들이 어떻게 치환됐는지 확인해보자.

일반화하여 NxN으로 확장시켜보자.

let arr = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]];
const square = 4;

let origin = arr.map(v => v.slice());
for (let i = 0; i < square * square - 1; i++) {
  let tmp = origin.map(v => v.slice());
  let tmp_num = origin[i%square][Math.floor(i/square)];
  if (Math.floor(i/square) < i%square) {
    tmp[i%square][Math.floor(i/square)] = origin[Math.floor(i/square)][i%square];
    tmp[Math.floor(i/square)][i%square] = tmp_num;
  }
  origin = tmp.map(v => v.slice());
}

for (let i = 0; i<4; i++)
  console.log(origin[i]);

TL;DR

우리는 복잡도가 높은 알고리즘을 줄이기 위해 반복되는 패턴을 찾아 해결하려고 한다.
주로 우리는 재귀 함수로 그 패턴을 처리하는데, 크롬의 경우 꼬리물기를 지원하지 않아서 허용되는 Call Stack의 개수가 생각보다 많지 않아서 언제나 Stackoverflow의 가능성이 항상 존재한다.

모든 꼬리물기 재귀 함수는 for문으로 치환할 수 있다. 이를 통해, 우리는 재귀 함수의 Stackoverflow의 가능성을 피할 수 있다.

우리는 이제 재귀 함수로 먼저 문제를 풀고, 재귀 함수를 꼬리물기 가능한 재귀함수로 바꾸고, 꼬리물기 가능한 재귀함수를 for문으로 치환해서 조금 더 나은 알고리즘을 짤 수 있다.
어떤 복잡한 문제일지라도 꼬리물기 가능한 재귀함수를 만들 수만 있다면 기계적으로 for문으로만 구성된 알고리즘을 만들 수 있을 것이다.