[Note] 꼬리재귀 최적화에 대한 고찰

[saseungmin]

• 1부터 n까지의 합 구하기를 풀면서 생각한 방법은 재귀호출이였다.

function solution(n) {
  if (n > 20) {
    return false;
  }

  if (n < 1) {
    return 0;
  }

  return n + solution(n - 1);
}

• 하지만 위와 같이 재귀를 하면 아직 연산이 안 끝났기 때문에 계속 스택이 싸이면 당연히 스택 오버 플로우가 발생하게 된다.
• 그래서 연산이 안끝나는 재귀를 해결하기 위해서 꼬리재귀를 한 번 시도해봤다. 꼬리재귀를 사용하면 연산이 종료되고 다음 연산이 진행되기 때문에 스택 오버 플로우가 발생하지 않는다.
• 다만, 현재 지원하는 브라우저가 없다.. 뭐.. Firefox에서만 지원한다고는 하는데.. 이 마저도 완벽하게 안된다는 소리를 들었다.
• 어쨌든 그냥 저렇게 재귀를 사용하면 가독성에는 좋겠지만, 그냥 반복으로 구현하는 거 보다 성능에 있어서는 좋지 못하기 때문에 그냥 반복으로 구현하는게 좋다고 생각한다.
• 꼬리재귀를 구현해 본적이 없어서 간단한 예제라 한 번쯤은 시도해보고 싶었다.
• 하지만, 아래와 같이 꼬리재귀 호출을 적용했을 때는 문제에서 원하는 방향성과는 다를 수 밖에 없었다. 여기서 주어진 문제는 파라미터를 하나만 넘기지만 꼬리재귀를 하면 함수를 리턴해야하기 때문에 커링을 사용하여 함수를 리턴해줘야 한다.
• 만약 커링을 사용하지 않는 다른 방법은 파라미터를 두 개를 넘기는 것뿐이다.
• 다음과 같이 꼬리재귀를 적용하면 코드도 반복문으로 구현하는 것보다 가독성도 좋고 성능 또한 같다.
• 꼬리재귀가 잘 되었는지 확인하는 방법은 다시 반복문(for)으로 변경해봤을 때 반복문으로 변경이 되면 꼬리재귀가 잘 되었다는 증거이다. 만약, 꼬리재귀가 안되어 있으면 반복문으로 변경할 수 없다.
• 변경해보는 건 좀 더 고민해봐야겠다. 어떻게 변경해보라는건지 잘 모르겠다.

function solution(n) {
  return function (acc = 0) {
    if (n > 20) {
      return false;
    }

    if (n < 1) {
      return acc;
    }

    return solution(n - 1)(acc + n);
  };
}

test('Should return the sum from 1 to n', () => {
  expect(solution(6)()).toBe(21);
  expect(solution(10)()).toBe(55);
});

[saseungmin]

• 다음과 같이 변경하면 기존의 문제가 원하는 형태로 재귀 함수를 사용할 수 있다.
• 또한, 바로 자기 자신만을 리턴하고 남아있는 연산이 없기 때문에 꼬리재귀 최적화도 가능해졌다.

function solution(n) {
  function calculate(k, acc) {
    if (k < 1) {
      return acc;
    }

    return calculate(k - 1, acc + k);
  }

  return calculate(n, 0);
}

test('Should return the sum from 1 to n', () => {
  expect(solution(6)).toBe(21);
  expect(solution(10)).toBe(55);
});

[saseungmin]

• 비슷한 문제로 팩토리얼도 꼬리재귀 최적화를 시켜 재귀를 사용하여 문제를 풀 수 있다.

function solution(factorial) {
  function dfs(n, acc) {
    if (n === 1) {
      return acc;
    }

    return dfs(n - 1, acc * n);
  }

  return dfs(factorial, 1);
}

describe('solution', () => {
  it('팩토리얼한 값을 반환해야 한다.', () => {
    expect(solution(5)).toBe(120);
  });
});