재귀,,, 우리 재귀는요 데이터 구조를 검색할 때도 유용하구요,,⭐️
재귀는 강력한 함수형 기법이다. 하지만? 그래.알아보자.
재귀 (recursion)
재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있습니다.
모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아닙니다.
우리가 필요한 것은 좋은 코드입니다. 이런 이유 때문에 재귀를 사용합니다.
재귀는 자기 자신을 호출하는 함수를 만드는 기법이다.
기본적으로 재귀는 반복문과 동일한 결과?를 얻을 수 있지만
단순화하여 훨씬 간결하게 표현할 수 있다는 장점이 있다.
map, filter, reduce와 같은 함수들은
파라미터로 다른 함수(콜백 함수)를 받는 고차 함수다.
만약 함수에서 다른 함수를 호출해야하는데 그게 바로 나라면?
그게 바로 재귀 함수이다.
// 만약 기존의 for루프를 돌려 10부터 0까지 카운트 다운하는 코드를 작성한다면
// 아래와 같을 것 이다.
const MAX_COUNT = 10;
for(let i=MAX_COUNT; i>=0; i--){
console.log(`${i}!!!`);
}
//해당 코드를 재귀로 표현한다면?
const countdown = (val, fn) => {
fn(val);
return (val > 0)? countdown(val-1, fn) : val;
}
countdown(10, val => console.log(val));
이렇게 재귀 함수는 걸어놓은 조건에 만족할 때까지 반복하여 자신을 호출한다.
(⚠️ 조건을 생략한 채 재귀함수를 실행하게되면 무한루프에 빠져버린다...! ⚠️)
만약 1부터 n까지의 숫자를 더하는 함수를 작성한다면,
아래와 같은 방법들로 작성할 수 있다.
가장 빠른 방법은 세 개의 연산만을 수행하는 등차수열일 것 이다...!
두번째로는 반복문, 마지막이 재귀 함수일 것이다. (재귀를 사용하기 위해서는 중첩 호출과 스택 관리가 추가로 필요하다..*)
//반복문
const forLoop = (n) => {
let sum = 0;
for(let i=0; i<=n; i++){
sum += i;
}
return sum;
}
//재귀
const recursion = (n) => (n == 1)? 1 : n + recursion(n-1);
//등차 수열
const as = (n) => n*(n + 1)/2;
또 다른 예로 팩토리얼을 살펴보자.
const factorial = (n) => (n!=1)? n * factorial(n - 1) : 1;
console.log('factorial :: ', factorial(100)); //9.33262154439441e+157
console.log('factorial :: ', factorial(1000)); //Infinity
console.log('factorial :: ', factorial(10000)); //Maximum call stack size exceeded
해당 팩토리얼 함수를 실행하다보면
factorial(10,000) 정도부터 'Maximum call stack size exceeded' 라는 에러를 마주할 수 있다 ㅎㅎㅎㅎ
말그대로 stackoverflow!!!
한 두번 실행이 아닌 1,000번, 10,000번 실행하게 된다면?
콜 스택에 계속 쌓이고 있던 그 규모는 생각보다 눈덩이처럼 불어나버린다.
메모리의 용량은 한정적이고 결국 넘쳐버리게된다. ㅠㅠ
이렇게 재귀는 무리한 재귀 호출은 스택 오버플로우를 야기할 위험성을 내재하고 있다는 점도 주의해야한다..!!
다음 번엔 재귀의 단점을 보완한 꼬리 재귀에 대해 알아보자.
꼬리물기 최적화 (Tail recursion)