소개
재귀는 함수가 자기 자신을 호출하는, 프로그래밍에서 아주 강력한 개념이에요.
처음에는 조금 어렵게 느껴질 수 있지만, 기본 원리를 이해하고 나면 복잡한 문제를 해결하는 데 유용한 도구가 돼요.
이번 튜토리얼에서는 따라 하기 쉬운 예제와 함께 JavaScript의 재귀를 살펴봐요.
재귀란 무엇일까요?
재귀는 함수가 직접 또는 간접적으로 자기 자신을 호출할 때 일어나요.
루프와 비슷하지만, 문제를 더 작고 다루기 쉬운 하위 문제로 나눈다는 점이 달라요.
예제 1: 카운트다운
간단한 예제부터 시작해 볼까요? 카운트다운 함수예요.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
이 예제를 보면:
-
기저 조건:
num이 0보다 작거나 같아지면 함수는 "Blastoff!"를 출력하고 자기 자신을 호출하는 것을 멈춰요.
-
재귀 조건: 함수는 현재
num을 출력하고 num - 1을 인자로 자기 자신을 호출해요.
예제 2: 팩토리얼
이번에는 재귀의 고전적인 예제인 팩토리얼 계산을 살펴봐요.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
이 예제를 보면:
-
기저 조건:
n이 0 또는 1이면 함수는 1을 반환해요.
-
재귀 조건: 함수는
n에 n - 1의 팩토리얼을 곱해요.
핵심 개념
기저 조건
모든 재귀 함수에는 자기 자신을 호출하는 것을 멈추는 조건인 기저 조건이 적어도 하나 있어야 해요.
기저 조건이 없으면 재귀가 끝없이 이어져서 스택 오버플로가 발생해요.
재귀 조건
재귀 조건은 함수가 문제를 더 작고 단순한 형태로 만들어 자기 자신을 어떻게 호출하는지를 정의해요.
재귀의 장단점
장점:
- 특정 문제에서는 우아한 해결책이 돼요.
- 수학적 귀납법과 비슷한 방식이에요.
단점:
- 반복문을 사용한 해결책보다 효율이 떨어질 수 있어요.
- 재귀가 깊어지면 스택 오버플로가 발생할 수 있어요.
마무리
재귀는 복잡한 문제를 더 작고 다루기 쉬운 하위 문제로 나누어 단순하게 만들어 주는 유용한 기법이에요.
JavaScript에서 효과적인 재귀 해법을 구현하려면 기저 조건과 재귀 조건을 이해하는 것이 중요해요.
더 알아보기:
지침
피자 가게를 운영하는데, 세 가지 종류의 피자를 판매해요:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
손님이 원하면 추가 옵션을 개수 제한 없이 더할 수 있는데, "ExtraSauce"는 $1, "ExtraToppings"는 $2예요.
이번 과제는 고객이 비용을 계산할 수 있도록 도와주는 코드를 작성하는 거예요.
피자 한 판의 가격 계산하기
피자 이름을 첫 번째 인자로 받고, 추가 옵션은 개수 제한 없이 받은 뒤, 피자의 가격을 달러로 계산해요.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
주문 전체의 가격 계산하기
함수는 PizzaOrder 목록과 함께 호출되고, 주문의 총 가격을 달러로 반환해야 해요.
각 PizzaOrder에는 pizza 속성(피자 이름)과 extras 속성(추가 옵션 목록)이 있어요.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
주문이 엄청나게 많은 테스트 하나가 Maximum call stack size exceeded를 발생시키기 때문에, 재귀로는 이 함수를 작성할 수 없다는 걸 알게 될 거예요.
걱정 마세요, 이건 의도된 거예요. 명령형 루프를 사용해서 이 함수를 구현해 봐요!
reduce나 for문을 사용하는 것 등, 여러 가지 방법이 있어요. (이것들로만 국한되지는 않아요.)
JavaScript 인터프리터가 JavaScript 코드를 실행할 때는, 어떤 함수에 진입했는지(호출하기 시작했는지)를 "스택"이라는 자료 구조에 기록해요.
함수가 반환되면(끝나면) 스택에서 제거돼요.
그런데 이 스택은 크기가 제한되어 있어요.
가장 흔한 실수는 끝나지 않는 재귀 함수예요.
호출이 스택에 쌓이는데, 반환되기 전에 또 다른 호출이 스택에 쌓여요.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
이 오류의 스택 트레이스는 같은 줄을 계속 보여주는데, 함수가 자기 자신을 호출하니까 당연한 일이에요.
대부분의 경우 실용적인 쓰임은 없지만, 스택이 얼마나 높이 쌓일 수 있는지는 알아낼 수 있어요.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
동기 재귀 함수 때문에 발생하는 호출 스택 오류를 해결하는 방법은 딱 두 가지예요:
- 스택 한계에 도달하기 전에 함수가 반환되도록 만들어요. 보통은 베이스 케이스를 추가하거나 고치는 방식이에요.
- 재귀 함수를 명령형 루프로 다시 작성해요. 그러면 함수에 진입하지 않고 루프의 본문을 실행하므로 스택이 늘어나지 않아요.
학습 연습 문제
