재귀함수와 메모리 사용량 간의 관계

재귀함수는 함수의 호출이 반복적으로 이루어지기 때문에 성능에 좋지 않다고 한다. 자칫 스텍 오버플로우를 일으킬 수 있다.
그렇다면 우리는 왜 재귀함수를 쓰는가? 거기에 대한 해답이다

• 알고리즘 자체가 재귀적으로 표현하는게 가독성이 좋을 때
• 변수 사용량을 줄일 수 있다.
  여기서 변수 사용량을 줄인다는 말은 말 그대로 메모리에 잡히는 변수를 줄여준다는 뜻이 아니다. mutable state(변경가능 상태)를 제거해서 오류 발생 확률을 낮출 수 있다는 뜻이다.

꼬리재귀

앞서 말한 재귀함수는 장점과 단점을 가지고 있는데 단점을 보완하기 위한 최적화 방법을 꼬리재귀라고 한다.

꼬리재귀란, 재귀호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태이다. 이는 컴파일러가 선형으로 처리하도록 알고리즘을 바꿔서 스택을 재사용 가능하게 한다. (단, 컴파일러가 이 기능을 지원해야 가능)
아래의 코드는 일반적인 재귀함수와 꼬리재귀를 나누어 둔 것이다.

일반적인 재귀함수

function fac(n){
  if(n === 1){
    return n;
  }
  return n*fac(n-1);

꼬리재귀

function fac(n){
  if(n === 1){
    return n;
  }
  let result = fac(n-1);
  return n*result;
  

단순하게 본다면 두 코드의 차이도 없고 결과 또한 똑같이 나올 것이다. 하지만 스텍창을 확인하면 일반적인 재귀함수는 스텍이 계속 쌓이게되고 꼬리재귀는 한번만 호출 될 것이다. 단순하게 말해서 일반적인 재귀함수는 리턴 값이 함수이기 때문에 계속 해서 함수를 호출한다.
하지만 꼬리재귀의 경우는 함수를 호출하고 그 함수를 변수에 할당하고 사용한다. 이 처럼 더 이상 함수에서 추가 연산이 일어나지 않는다. 이 처럼 스텍이 계속 쌓이는 재귀의 단점을 보완한 것이 꼬리함수 이다.

하노이의 탑 재귀

간단하게 말하면 접시 A, B, C가 있는데 A점시에 빵이 큰 순서대로 쌓여있다고 가정해보자. A접시에 있는 빵을 전부 B나 C의 접시에 옮기기 까지 빵을 몇번 옮겨야 할까? 라는 질문이다. 단, 빵 위에 올라가는 빵은 밑에 있는 빵보다 클 수 없다.

hanoi(N): 빵 개수 N을 입력 받아 모든 빵을 'C' 접시에 옮기는 각 움직임을 출력한다.