자 일단 재귀함수를 왜 사용할까? 사실 재귀함수로 작성 할 수 있는 모든 알고리즘은 반복문으로 작성할 수 있으며, 모든 반복문 또한 재귀함수로 작성 할 수 있다. 하지만, 여기서 반복문으로 작성한다는 것 자체는 명령형 스타일의 코드이고, 재귀 함수를 작성한 다는 것은 선언형으로 작성한다는 것이다.
명령형과 선언형 중에 선언형이 의미 파악이 더욱 파악하기 쉽다.
자 간단하게 아래의 함수를 보자.
function foo(n = 0) {
if(n === 0) return 0
let res = 1
for(let i = n; i >= 1; i--) {
res *= i
}
return res;
}
자 간단하게 위의 코드를 보자. foo라는 함수는 n의 값을 하나씩 줄이면서 기존 결과에 값을 곱하게 된다.
function bar(n = 0) {
if(n === 0 || n === 1) return n;
return n * bar(n - 1)
}
자 위의 코드를 보자 bar의 경우에는 종료 시점 0, 1과 현재의 n과 bar(n-1)을 곱한다. 라는 식처럼 보인다.
자 우리는 팩토리얼을 구현한 것이다. 아래의 정의를 보았을 때, foo와 bar중에 어떤 모양이 팩토리얼의 정의에 더 비슷한 모양인가?
n
!
=
n*
(
n-
1
)
*
(
n-
2
)
*
...
*
1
특히 수학의 반복의 표현에서는 대부분의 경우, 재귀로 표현하는 것이 구현 및 의미파악이 더 쉽게된다.
function bar(n = 0) {
if(n === 0 || n === 1) return n;
return n + bar(n - 1)
}
자 간단하게 위의 코드로 변경해보았다. 그냥 1 + 2 + 3... 이런식으로 더하는 코드이다.
자 재귀의 가장 큰 문제는 이것이다. 기본적으로 브라우저에서 사파리를 제외하고는 꼬리재귀 최적화가 되어있지 않기 때문에, 위와 같은 문제가 발생할 것이고, 반복문에 비해 환경정보를 생성해야 해서 매우 느릴 것 이다.
뭐 물론 속도면만 생각하지 않는다면, 위의 오류를 제어 할 수 있다.
const getMaxCallStackSize = (i) => {
try {
return getMaxCallStackSize(++i);
} catch {
return i;
}
};
console.log(getMaxCallStackSize(0));
자 간단하게 콜스택사이즈 최대 사이즈를 구할 수 있는 코드이다.
10448 생각보다 작다..
function bar(n) {
return new Promise((resolve, reject) => {
if (n === 0 || n === 1) {
resolve(n);
return;
}
Promise.resolve(n).then(n => bar(n - 1)).then(prev => resolve(n + prev));
});
}
꽤나 오래걸리긴 했지만, 재귀코드로 작성했을에도, Maximum callstack size가 발생하지 않았다. 메모리면에서 이득을 가져갈 수 있다는 뜻이다.
사파리의 경우 TCO가 되어있기 때문에, 꼬리재귀 형태로 작성하였다면 , Maximum callstack에러가 발생하지 않을 것이다.
댓글
댓글 쓰기