[JS 알고리즘] 재귀(Recursion)
1
재귀 함수를 사용하는 이유
- What is recursion?
- 재귀란 자기자신(함수)을 호출하는 과정이다. A process (a function in our case) that calls itself
- 왜 알아야 하는가?
- 어디에나 있기 때문이다.
- JSON.parse / JSON.stringify
- 브라우저 엔진에서 JSON 타입은 보통 재귀를 사용하게 된다.
- document.getElementById 와 DOM 순회 알고리즘들
- DOM은 트리 구조라서 중첩 구조가 아주 많다. 어떤 경우에는 div 안에 div 안에 div가 반복되는 100겹의 중첩구조가 있을 수도 있다. 이 모든 것을 통해서 탐색할 때 재귀를 쓸 수 있다.
- Object 순회
- 이외에도 복잡한 데이터 구조들에서 해결 방안으로 종종 재귀가 포함된다.
스택 호출하기
- 재귀 함수가 스스로를 계속해서 호출한다면 그 뒤에서는 무슨 일이 일어날까? 오류 없이 효과적인 재귀 함수를 작성하기 위해 이해해야만 한다.
- 거의 대부분의 프로그래밍 언어는 함수가 호출되면 뒤에서 관리하는 데이터 구조가 있는데, 자바스크립트에서는 그것을
call stack이라고 부른다.- 함수 하나가 호출되면 호출 스택의 맨 위에 놓인다. 컴파일러는 스택의 제일 위에 있는 것을 실행하고 제거한다.
- 예시
- 브라우저 개발자도구 스니펫에 코드를 붙여넣고, 함수 호출문에 breakPoint를 걸고 Ctrl Enter로 실행 후, F9를 누르면서 콜스택의 흐름을 확인해보자.
function takeShower() {
return "샤워하자"
}
function eatBreakfast() {
let meal = cookFood()
return `${meal}를 먹자`
}
function cookFood() {
let items = ['김치찌개', '미역국', '된장찌개']
return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
console.log(takeShower());
console.log(eatBreakfast());
console.log("이제 출근하자")
}
wakeUp();- 재귀 함수를 작성하게 되면 콜 스택을 가지고 작업을 해야 하는 경우가 많다.
- 재귀함수에서는 호출 스택에 새로운 함수(같은 함수)를 계속해서 밀어 넣는다.
- JSON.parse가 JSON.parse를 계속해서 호출한다는 것을 가정해보면, 호출 스택에는 JSON.parse 위에 JSON.parse, 그 위에 JSON.parse 이런 식이 된다. 그리고 어느 순간에는 멈춘다(조건을 줘서 멈춰야 한다).
- 재귀함수에서는 호출 스택에 새로운 함수(같은 함수)를 계속해서 밀어 넣는다.
재귀함수에서 필수적인 두 가지 부분
- 재귀 함수에서 필수적인 두 가지 부분
- Base Case
- Base Case란 재귀가 멈추는 조건이다.
- 다른 입력값
- 같은 함수가 호출되더라도 매 번 다른 데이터가 입력되어야 한다.(줄어든다)
- Base Case
function countDown(num) {
if(num <= 0) { // 1. Base Case
console.log("All done!");
return;
}
console.log(num);
num--; // 2. 매번 다른 값 입력
countDown(num);
}
countDown(5);// 재귀를 이용한 sum 함수
function sumRange(num) {
if(num === 1) return 1; // Base Case
return num + sumRange(num-1); // 다른 input
}
sumRange(3) // 6
// return 3 + sumRange(2);
// return 2 + sumRange(1);
// return 1;// 재귀를 이용한 팩토리얼 함수
function factorial(num) {
if(num===1) return 1; // Base Case
return num * factorial(num-1); // 다른 input
}
factorial(4)재귀를 잘못 쓰는 경우
- 재귀를 잘못 쓰는 경우
- Base Case를 두지 않는 경우
- 반환하는 것을 깜박했거나 잘못된 것을 반환하는 경우
- Stack overflow
- 재귀가 멈추지 않아 스택에 함수 호출이 너무 많이 쌓여서 최대 콜스택 사이즈를 초과한 경우
- 호출 스택을 두고 보면 모든 것들이 서로에게 의존한 채로 서로를 기다리고 있는 것이다. 마치 사슬에 묶여 있는 것과 비슷한데 마지막에 어떤 값이 되돌아오면서 그걸 더하거나 곱하는 것처럼 작업을 해서 그 이전으로 돌려보내서 마지막으로 원래 함수호출문에 영향을 주는 것이다.
재귀의 두 가지 디자인 패턴
1. Helper 메소드 재귀
- 재귀와 함께 흔히 사용되는 디자인 패턴 중에 헬퍼 메소드 재귀가 있다.
- 나중에 반환할 값을 정의한 빈 배열을 재귀함수 안에 정의하면 재귀호출시마다 초기화되는 문제가 있으므로, 재귀함수 밖에 정의한다. 그리고 그 재귀함수를 감싸는 다른 함수를 만든다.
- 헬퍼 메소드 재귀는 재귀형이 아닌 외부 함수가 재귀형인 내부 함수를 호출하는 형태이다.
- 예시 (배열의 모든 홀수를 모으는 함수)
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])2. 순수(Pure) 재귀
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,5]);
// [1].concat(collectOddValues([2,3,4,5]))
// [].concat(collectOddValues([3,4,5]))
// [3].concat(collectOddValues([4,5]))
// [].concat(collectOddValues([5]))
// [5].concat(collectOddValues([]))
// []
// [1].concat([3].concat[5])
// [1,3,5]- 위 순수 재귀함수에서는 함수가 재귀적으로 호출될 때마다 반환값을 담을 배열이 초기화되어 빈 배열이 될 것이다. 하지만 여기서 다른 점은 거기에 신경 쓸 필요가 없다는 것이다. 이번에는 그렇게 작동하도록 의도하였다.
- 여기서는 배열들을 가장 뒷 부분에 합쳐준 다음에 다시 반환한다.
- 순수함수 사용 Tip
배열에서, slice와 같은 메서드나 spread 연산자, 그리고 concat 메서드를 사용해서 배열을 복사하고 그 배열을 변화시키지 않는다.문자열은 불변이므로, slice나 substr, substring과 같은 메서드를 사용해서 문자열을 복사할 수 있다.객체의 경우, Object.assign이나 spread operator를 사용하여 객체를 복사할 수 있다.- 이렇게 하면 결과값을 쌓아갈 수 있다.
HMMM...
블로그 이사 🚚 https://wonsss.github.io/