재귀
recursion
한 가지 문제를 가지고, 어떤 종료점(end point)에 도달할 때까지
더 작은 부분이나 변경되는 부분에서 반복적으로 수행하는 것을 재귀라고 한다.
그 종료점을 종료 조건(base case)라고 부른다.
재귀는 자기자신을 호출하는 절차이다.
재귀를 사용해서 코드를 더 깔끔하고 간단하게 만들 수 있다.
재귀는 어디에나 사용된다. JSON.parse나 getElementById 같은 기능에도 재귀가 사용된다.
Call Stack(호출 스택)
콜스택
거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 데이터 구조가 있다.
호출된 함수는 다른 함수가 반환(return) 될 때까지 기다리는 경우가 많다.
이런 순서는 무작위가 아니다. 제일 먼저 호출한 함수가 있고 그 함수 안에 두번째 함수를 호출한다.
그걸 담당하는 데이터 구조가 자바스크립트의 경우 콜스택이다.
콜스택은 종이 더미 같은 것이다.
함수를 호출하면 콜스택의 꼭대기에 쌓인다. 책상에 있는 종이 더미처럼 그 맨 위에 쌓인다는 것.
무언가를 다시 꺼낼때, 꼭대기에서부터 꺼낸다. 밑에서부터 꺼내지 못한다.
이게 콜스택의 개념이다.
chrome개발자 도구에서 콜스택을 확인 할 수 있다.
함수를 호출하면 함수가 스택의 꼭대기에 추가되고, 마찬가지로 꼭대기에서 한번에 하나씩 제거된다.
함수가 return하면 꼭대기에서 제거 된다.
재귀 함수를 사용하면 콜스택을 엄청나게 많이 사용한다. 일반 함수는 콜스택이 바로 밀려나지만
재귀함수는 콜스택을 엄청나게 많이 쌓은 후, 맨 끝에 꼭대기에서부터(종료지점) return하면서 돌아온다.
콜스택은 자바스크립트 보이지 않는 곳에서 작동하는 정적 데이터 구조(static data structure)이다.
재귀 호출 & 중단점
재귀함수는 두가지 조건이 있다.
- 자기 자신을 재귀적으로 호출할 것
- 중단점이 있을 것
중단점 = 종료 조건이 있어야 한다.
종료 조건은 재귀가 멈추는 시점이다.
중단점이 없으면 재귀적으로 자기자신을 호출하는 것이 영원히 계속된다.
function sumRange(num){
if(num === 1) return 1;
return num + sumRange(num-1);
}
sumRange(4)재귀적으로 자기 자신을 호출할때는 애초에 입력받은 변수 num과 다른 값을 넣어 호출해야 한다.
-1씩 줄여서 호출하는 것이다 .똑같이 num을 넣으면 무한 반복→ 스택 오버플로우다.
중단점은 return 1 이다. 종료 조건은 num = 1 이 될때까지 콜스택이 쌓였다가 다시 하나씩 return되며 사라지는 것이다.
반복문과 재귀 호출 비교
팩토리얼을 반복문으로 구현했을 때
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);
}재귀함수를 쓸 때 실수하는 포인트
- 종료 조건이 없는 것
- 값을 반환하는 걸 잊는 것
- 잘못된 값을 반환하는 것
→ 스택 오버플로우 발생!
Helper method recursion
이제까지 재귀함수는 팩토리얼 처럼 단일 단독 함수(single standalone function)
함수 외부에서 팩토리얼을 호출하면, 팩토리얼은 직접 자체 코드 내 팩토리얼을 호출.
헬퍼 메소드 재귀는 다르다.
헬퍼 메소드 재귀에는 두 개 함수가 있음.
외부 함수와 그 안에 있는 헬퍼 함수.
외부 함수는 재귀적이지 않다.
그 안에 헬퍼 함수는 재귀 함수이다. 그 재귀적인 내부 함수가 반복되며
외부 함수 안에 있는 result에 값을 넣고 재귀가 끝나면
외부 함수에 result를 return 하는 구조이다.
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])collectOddValues는 외부함수. helper함수는 재귀함수인 내부함수이다. result는 외부함수 스코프에 존재. 헬퍼함수가 재귀를 돌리면서 result에 결과를 넣는다. 그리고 result를 외부함수가 반환.
헬퍼 메소드 재귀는 직관적이다.
Pure recuresion(순수 재귀)
헬퍼 메소드 재귀를 사용하지 않고 순수 재귀만 사용
헬퍼 메소드 재귀가 조금 더 직관적. 순수 재귀는 약간 이해하기 어렵다
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])맨 앞에 요소를 뺀 배열을 변수로 하여 재귀를 돌린다. 빈 배열부터 concat으로 합쳐서 리턴.
순수 재귀를 사용할때 팁
- 배열을 다룰 때, slice, spread 연산자, concat을 사용하면 복사하는 기능. 그 배열을 변경할 필요가 없다. 이걸로 결과를 축적할 수 있다.
- 문자열은 immutable이기 때문에 slice나 substring을 사용해서 사본을 만들어야 한다.
- 객체의 경우 Object.assign이나 spread 연산자를 사용하면 유용하다.
