🔄 재귀 - Recursion
어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 즉, 자기 자신을 호출하는 절차
1. 재귀가 쓰이는 곳
- 재귀는 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때
- javascript 내부에서는?
- JSON.parse / JSON.stringify
- document.getElementById, querySelector and DOM 탐색 알고리즘(*DOM은 요소가 중첩된 트리 구조)
- 객체 순회
- 복잡한 데이터 구조 (데이터 구조, 트리, 그래프)를 순회, 그 안에 있는 요소 검색 하는 경우
✋ 잠깐! 재귀를 이해하려면 Call Stack에 대해 알아야함
- JavaScript는 단일 스레드 프로그래밍 언어이므로, 단일 호출 스택이 존재.
=>한 번에 하나의 일(Task)만 처리할 수 있다 - 함수를 실행하면 해당 함수의 기록을 스택 맨 위에 추가(Push) ,
함수를 결과 값을 반환(함수가 종료)하면 스택에 쌓여있던 함수는 제거(Pop)되며 동작한다.
지금은 간단히 기록, 따로 콜스텍과 자바스크립트 엔진이 돌아가는 원리에 대해서 정리해 볼 예정이다!!!
2. 재귀 함수 (Recursion Function)
동일한 함수를 계속 호출하면서 하나의 함수가 자신을 재귀적으로 호출
(중단 포인트를 만날 때 까지 같은 함수를 계속 호출)* 중단 조건 필수 -> stack overflow 현상이 일어남 * 매번 다른 input을 통해 호출되어야한다.
2-1. 재귀 함수의 잠재적 위험성을 초래하는 문제점
1. 종료 조건이 없거나 잘못 되는 경우
- 함수가 종료되지 않고 stack overflow로 종료됨 (엔진마다 호출 스택 크기가 정해져 있기 때문에)
return 으로 확실한 break point(base case)를 설정해줘야 한다.
2. 값을 반환하는 걸 잊는 것
- call stack의 경우 모든 항목이 서로에게 의존적이며 연결되어 있다 마지막에는 어떤 값을 도출해서 그 값을 돌려보내야 한다
3. 잘못된 값을 반환 하는 것
💻 예제1
num까지의 합을 리턴하는 함수 sumRange를 작성하시오
const sumRange = (num) => {
if (num === 1) return 1; //base case (중단 조건)
return num + sumRange(num - 1); // 재귀호출 : 매번 더 작은 값으로 input 값을 받음
};💡 예제1 실행순서
실행순서 3 >> return 3 + sumRange(2)
실행순서 2 >> ................... return 2 + sumRange(1)
실행순서 1 >> ............................................ return 1
call stack의 상단의 연산부터 시작해 sumRage(1)의 리턴값 (재귀 종료)인 1부터 순서대로 ((1) + 2)+ 3 순서대로 sum 후 리턴
💻 예제2
Factorial 구하는 함수
팩토리얼 = 계승 : 1부터 n까지의 자연수를 모두 곱하는 것
풀어보기 전
1. num이 1이 되면 멈춘다 (0이되면 어떤 수든 리턴 값이 0이 됨)
2. 숫자를 1씩 줄여가면서 재귀 함수 호출 * 인자로 받은 num 곱해줌 => num이 1이 될 때 까지 재귀 호출
const getFactorial = (num) => {
if (num === 1) return 1;
return num * getFactorial(num - 1);
};3. Helper Method Function
재귀적이지 않은 외부 함수가 재귀적인 내부 함수(inner function)을 호출하는 패턴이다. 문제 해결을 위한 하나의 접근법이다.
- 헬퍼 함수 혹은 헬퍼 메소드 재귀라고 부른다.
- 메인 외부 함수를 개발자가 외부에서 호출한다.
- 이 외부 함수를 호출할 때 인자를 내부로 전달해 줄 수 있다.
- 이 외부 함수 내부에는 또 다른 내부 함수가 정의되어 있다. 내부함수는 호출되고 재귀적으로 자기자신을 호출한다.
- 결과를 컴파일할 때 흔히 사용 결과는 배열과 다른 형태의 데이터 구조이다.
기본형태
const outer = (input) => {
const outerScopedVar = []; // array or list of data
const helper = (helperInput) => {
//outerScopedVar 변경
helper(helperInput--); // 인풋 값 감소
};
helper(input);
return outerScopedVar;
};💻 사용 예
어느 배열에서 홀수 값을 구하는 것 같은 작업
const collectOddValues = (arr) => {
const result = [];
const helper = (helperInput) => {
if (helperInput.length === 0) return;
if (helperInput[0] % 2 !== 0) result.push(helperInput[0]);
helper(helperInput.slice(1));
};
helper(arr);
return result;
};
//재귀 함수를 내부 호출히서 쓰는 위의 패턴이 아닌 재귀만 사용해서 풀이
const collectOddValues2 = (arr) => {
let newArr = []; // 내부에 요소를 추가해주는 게 아닌 배열을 합쳐서 새 배열을 할당해야 하므로 let으로 선언
if (arr.length === 0) return newArr;
if (arr[0] % 2 !== 0) {
newArr.push(arr[0]);
}
console.log(newArr);
newArr = newArr.concat(collectOddValues2(arr.slice(1)));
return newArr;
};
collectOddValues2([1,2,3,4,5]) 재귀 동작 방식
실행완료순서6 >> [1].concat(collectOddValues2([2,3,4,5]))
실행완료순서5 >> ...... [].concat(collectOddValues2([3,4,5]))
실행완료순서4 >> ............ [3].concat(collectOddValues2([4,5]))
실행완료순서3 >> .................. [].concat(collectOddValues2([5]))
실행완료순서2 >> ........................ [5].concat(collectOddValues2([]))
실행완료순서1 >> ................................ []
3. 순수하게 재귀 함수만 사용하여 구성할 때 사용하는 Method
자료형에 맞게 복사본을 만들어 진행 => 변경 할 필요 없음 , 결과를 축적할 수 있음
-
array : array.slice(), spread operator , array.concat()와 같은 배열을 복사하는 메서드를 사용
-
String : immutable(변경할 수 없음)하기에 slice, substr, substring 같은 메서드를 통해 문자열의 사본을 만들어 진행
-
Object : Object.assign , spread operator를 이용해 복사본 만들어 사용
