재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
함수를 재귀적으로 호출하여 문제를 해결하는 방식은 코드를 간결하고 의도를 파악하기 쉽게 작성할 수 있는 장점이 있다. 하지만 재귀함수의 콜스택이 깊어 질수록 메모리 오버헤드가 발생하는 단점도 있다.
꼬리 재귀 (tail recursion in js)
이 문제를 해결하기 위한 재귀 호출 방식을 꼬리 재귀라고 부른다.
간단하게 정의하자면
재귀함수의 실행 결과가 연산에 사용되지 않고 바로 반환되게/ 함수가 Return 명령어를 만나기 바로 직전에 호출되게(Tail call)
함으로써 이전 함수의 상태를 유지할 필요가 없도록 재귀 함수를 작성하는 것이다. (꼬리 재귀가 동작하려면 플랫폼에서 TCO(Tail Call Optimization)를 지원해 줘야한다. 하지만 안타깝게도 safari 를 제외한 모든 브라우저는 TCO를 지원하지 않으며 node 역시 TCO를 지원하지 않고 있다.)
이때의 직전, 혹은 마지막이란 위치 개념은 컴파일 이전의 코드에서의 개념이 아닌, 실제 스택 프레임의 할당 해제 가 일어나기 직전의 위치를 뜻한다.
그러므로 다음과 같은 경우는 코드의 마지막에 위치하지만 Tail Call에 해당하지 않는다.
// 일반 재귀
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
//----------------------------------------------------
// 꼬리 재귀
function factorial(n, total = 1) { // default parameter :total이 제공되지 않으면 기본값으로 1을 할당한다
if (n === 0) {
return total
}
return factorial(n - 1, n * total)
}
//2개의 인자를 전달하고 있다. 다음 팩토리얼을 계산하기 위한 수인 (n - 1), 그리고 누적된 총합 n * total 이다.
//현재 상태를 실행하기 위한 모든 값 (누적된 값과 다음 팩토리얼 값)을 다 갖고 있기 때문에
//다음 호출이 더이상 이전 호출에 의존적이지 않음
//-----------------------------------------------
return func(n--); // 꼬리 호출이 아니다. (호출이 일어난 뒤, n의 감소가 이루어진다)
// 만약 위 코드가 `return func(--n)` 였다면, 꼬리 호출이다.꼬리 재귀 함수를 만들기 위한 팁은 이전 프레임을 제거할 수 있도록 다음 호출을 할 때 필요한 모든 “상태”를 넘겨주는 것이다. 단일 함수만을 가지고 항상 가능하지는 않으므로, 꼬리 재귀가 가능한 중첩 함수를 만들 수 있는지도 고려해볼 수 있을 것이다.
또하나 명심해야 할 것은, 적절한 꼬리 호출이 코드 실행을 반드시 빠르게 해 주는 것은 아니라는 것이다. 사실은, 오히려 느리게 만드는 경우가 대부분이다.
하지만, 꼬리 함수를 사용하게 되면 스택을 위한 메모리를 더 적게 사용할 수 있을 뿐만 아니라 국지적으로(locally) 할당된 객체들을 갖게됨으로써, 적은 메모리만 갖고도 재귀 함수를 실행할 수 있게 된다.
TCO(Tail Call Optimization)
마지막 호출에서 Call (Tail call) 을 하는경우, 새로운 스택 프레임 생성을 반복 하지 않고
같은 스택 프레임 내에서 다시 호출되는 함수의 진입점으로 Jump 하여 루틴을 진행할 수 있는것을 뜻한다(스택 프레임의 재사용 안전성).
그리고 Recursion 즉, 자기 자신을 호출하는 함수가 명령어의 가장 마지막에 위치할 때 이것을 Tail Recursion이라고 한다.
Tail Recursion Elimination
TCO(Tail Call Optimization)의 특별한 경우인 Tail Recursion Elimination 은 어떠한 함수가 꼬리재귀에 해당 할 때,
이를 반복문의 형태로 재구성 할 수 있는것을 뜻한다.
많이 착각하는 부분은, 꼬리 재귀의 형태로 구현이 되면 Tail Recursion Elimination이 된다고 생각하는 것인데,
이는 재구성 할 수 있다 라는 것이지 실제 컴파일러에서 최적화를 진행하지 않으면 일반적인 재귀와 마찬가지로 일반적인 Call이 이루어지게 된다.
하노이의 탑 재귀 (js tower of hanoi in recursion)
조합 재귀함수 (js combination in recursion)
조합과 순열의 근본적인 차이점 때문 : 순서의 여부
서로 다른 N개의 숫자 중 R개를 뽑는 경우의 수, 뽑는 순서는 상관 없다.[1, 2, 3] = [3, 2, 1]
배열의 처음부터 하나씩 선택(고정)하면서 뒤의 나머지의 배열에 대해서 조합을 구해서 붙이면 되는 것이다. 재귀함수로 들어가는 인자에 하나씩 줄여가며 넣어준다.
