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

실행 중인 함수의 실행 절차에 대한 정보는 함수의 실행 컨텍스트에 저장된다. 실행 컨텍스트는 함수 실행에 대한 세부정보를 담고 있는 데이터 구조이며, 제어흐름의 현재위치, 변수의 현재 값 등의 상세 내부정보가 담겨있다. 그러므로 함수를 호출할수록 실행 컨텍스트 계속 저장되기때문에 재귀의 깊이가 커지면 그만큼의 메모리를 차지하게 된다. 즉, 재귀함수를 쓸 수록 스택이라는 저장공간에 뭔가를 저장하기 때문에, 무리하게 호출하면 ‘스택오버플로우’가 발생할 수 있다.

• 꼬리재귀

꼬리재귀는 재귀호출이 끝나면 아무일도 하지 않고 바로 결과만 반환되도록 하는 방법이다.

일반 재귀는 값을 받으면, 그 값에 연산을 하고 다른 함수에게 전달하는 방식이지만, 꼬리재귀는 아무 추가적인 연산도 없이 값을 전달한다.

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

function factorial(n, total = 1){
    if(n === 1){
        return total;
    }
    return factorial(n - 1, n * total);
}

1번 코드와 같은 재귀함수를 아래의 꼬리함수처럼 이용할 경우 추가적인 연산 없이 매개변수의 전달인자만 변경되어 결과가 반환된다.

결론적으로 꼬리재귀는 자신이 호출한 함수한테 받은 결과값에 아무 연산도 추가적으로 하지 않고 반환하기 위해 마지막 꼬리부분에서 매개변수만 변경한 뒤에 함수를 호출하는 방식이다.

이해가 어려울 경우 아래 링크를 통해 학습하면 좋을 듯 하다.

꼬리 재귀 (Tail Recursion)

• 하노이 탑 재귀함수

아직 직접 코드를 짜보진 못했지만, 전체적인 코드가 이해는 되었다. 결국 하노이탑 실제 수행 순서를 반대로 생각하여 재귀함수를 통해 해결하는 것인데, 직접 코드를 짜보기 전에 아래의 링크를 통해 기본 개념을 학습하고 코드를 짜보면 좋을 것 같다. 나중에 시간이 될 때 시도해 보려고 한다.