📌 재귀(Recursion)란?
자기자신을 호출하는 함수를 의미한다.
필요성
- 다양한 솔루션에 활용된다.
ex. JSON.parse, JSON.stringify, document.getElementById, Object traversal - 반복 대신 재귀를 사용하는 게 더 깔끔할 때가 있다.
호출 스택(call stack)
- 호출 스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조(Static data structure)이다.
- 여러 함수들을 실행할 때 함수가 올바른 순서대로 실행되도록 하는 기능을 담당하는 자료 구조
스택(stack) 개념
스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out) 형식의 자료 구조이다.
새로 추가되는 함수는 호출 스택의 제일 꼭대기에 위치되고(push), return 키워드를 확인하거나 함수 안에 더이상 실행할 코드가 없으면 컴파일러가 스택 제일 위에 있는 항목을 제거한다.(pop)
비유하자면 종이 더미와 유사하다고 볼 수 있다.
-> 위에서만 종이를 넣거나 꺼낼 수 있다는 점에서 유사함.
예시
function takeShower(){
return "Showering!"
}
function eatBreakfast(){
let meal = cookFood()
return `Eating ${meal}`
}
function cookFood(){
let items = ["Oatmeal", "Eggs", "Protein Shake"]
return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
takeShower()
eatBreakfast()
console.log("Ok ready to go to work!")
}
wakeUp()
재귀함수의 두 가지 기본 요소
재귀함수란?
동일한 함수를 계속 호출하면서 하나의 함수가 자기자신을 재귀적으로 호출하게 하는 것을 말한다.
기본 요소
- 종료 조건(Base case)
재귀가 멈추는 시점을 정해주어야 한다. - 다른 입력값
원하는 결과가 나올 때까지 재귀함수에 각각 다른 입력값을 넣어주어야 한다.
⭐️ 재귀함수 예제 1 : n부터 1까지 출력하기
숫자 num이 주어질 때, num부터 1까지 1씩 감소된 값을 출력하기
반복문으로 구현하기(기존 방식)
// Iterative Version
function countDown(num){
for(var i = num; i > 0; i--){
console.log(i);
}
console.log("All done!")
}재귀함수로 구현하기
숫자를 출력하고 1씩 감소시키는 countDown 함수에 계속 새로운 입력값을 넣으며 0이 될 때까지 반복한다.
// Recursive Version
function countDown(num){
if(num <= 0) {
console.log("All done!");
return; // 종료
}
console.log(num);
num--;
countDown(num); // num에 1을 빼서 다시 호출
}
countDown(3)⭐️ 재귀함수 예제 2 : n부터 1까지의 합 구하기
num부터 1까지의 합을 출력하기
function sumRange(num){
if(num === 1) return 1;
return num + sumRange(num-1);
}
sumRange(3)
// return 3 + sumRange(2)
// return 2 + sumRange(1)
// return 1
// 값을 다 찾았으므로 거꾸로 더해줌.
// return 2 + 1
// return 3 + 3
// 6⭐️ 재귀함수 예제 3 : 팩토리얼 구현하기
재귀 함수 사용법을 가장 고전적으로 설명하는 것이 팩토리얼이다.
반복문으로 구현하기
function factorial(num){
let total = 1;
for(let i = num; i > 1; i--){
total *= i
}
return total;
}재귀함수로 구현하기
function factorial(num){
if(num === 1) return 1;
return num * factorial(num-1);
}⚠️ 재귀의 잠재적 위험
- 종료 조건이 없거나 잘못된 경우
- 잘못된 값을 반환하거나, 반환하는 걸 잊는 경우
=> stack overflow를 초래할 수 있다.
(재귀가 멈추지 않고 계속 반복됨.)
🔗 Helper 메소드 재귀(Helper method recursion)
-
재귀와 함께 사용되는 설계 패턴
-
재귀적이지 않은
외부 함수가 재귀적인내부 함수를 호출하는 패턴을 말한다.
예제
입력값으로 숫자를 담은 배열 arr이 주어질 때, 홀수만 배열에 담아서 반환하기
재귀적이지 않은 외부 함수 : collectOddValues()
재귀적인 내부 함수 : helper()
- 외부 함수인
collectOddValues()를 통해 입력값을 넘겨준다. - 결과값을 담을 빈 배열
result를 만든다. - 입력받은 배열의 맨 첫 번째 값이 홀수면
result에 값을 넣는 재귀함수helper()를 호출한다.(확인한 값은 slice하며, 입력값이 모두 없어질 때까지 반복함) result를 반환한다.
function collectOddValues(arr){
let result = [];
function helper(helperInput){
if(helperInput.length === 0) {
return;
}
if(helperInput[0] % 2 !== 0){
result.push(helperInput[0])
}
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
collectOddValues([1,2,3,4,5,6,7,8,9])🔗 순수 재귀(Pure Recursion)
-
필요한 모든 코드가 함수 자체에 포함되며 재귀적이다.
(재귀적이지 않은 외부 함수를 사용하지 않고, 오직 재귀함수 하나만 사용한다.) -
Helper 메소드 재귀를 이용하는 방식이 조금 더 직관적이라 Helper 메소드를 사용하는 것을 추천.
순수 재귀 팁
-
배열에서 Helper 메소드 없이 순수 재귀 솔루션을 작성하는 경우, 배열을 복사하는 slice, spread operator, concat과 같은 메소드를 사용하면 배열을 변경할 필요가 없다.
-
문자열은 변경할 수 없으므로 문자열을 복사하기 위해 slice, substr, substring과 같은 메소드를 사용하면 좋다.
-
객체를 복사하기 위해서는 Object.assign, spread operator를 사용한다.
위와 동일한 예제
순수 재귀로 풀어보기
function collectOddValues(arr){
let newArr = [];
if(arr.length === 0) {
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1,2,3,4])
// return [1].concat(collectOddValues([2,3,4]))
// [].concat(collectOddValues([3,4]))
// [3].concat(collectOddValues([4]))
// [].concat(collectOddValues([]))
// []
// [1,3,5]⭐️ arr.concat(arr)
: 여러 개의 배열을 합치는 메소드
ex. [1,3].concat([2,4]) -> [1,3,2,4]
추가 예제 : 피보나치 수열
Write a recursive function called fib which accepts a number and returns the nth number in the Fibonacci sequence. Recall that the Fibonacci sequence is the sequence of whole numbers 1, 1, 2, 3, 5, 8, ... which starts with 1 and 1, and where every number thereafter is equal to the sum of the previous two numbers.
function fib(n){
if(n === 1 || n === 2) return 1;
return fib(n-1) + fib(n-2);
}
fib(4) // 3
fib(10) // 55
fib(28) // 317811
fib(35) // 9227465