서론
오늘부터는 코드 리뷰에서 나와 다시 알고리즘 개념공부를 시작하도록 하겠다.
그 첫번째는 많이 들어보았지만 여전히 알듯말듯한 개념인 재귀이다.
재귀라는 단어에서 다시 불러온다는 의미를 유추할 수 있는데 과연 어떤 개념인지 알아보도록 하겠다!
본론
재귀란?
자신을 다시 호출하는 프로세스를 말한다.
재귀란 말 그대로 함수안에서 자기자신을 다시 참조하는 과정을 말한다.
예를 들어 10까지 카운트업을 하는 countUp이라는 함수가 있다. 아래는 단순히 for루프를 이용해 함수를 작성한 것이다.
function countUp(param){
if(param >= 10){
console.log("done");
return;
}
for(let i = param; i<=10; i++){
console.log(i);
}
console.log("done");
}이것을 재귀적으로 작성하면 다음과 같은 모습이 된다.
function countUp(param){
var num = param;
if(num >= 10){
console.log("done");
return;
}
console.log(num);
num++;
countUp(num);
}받은 숫자가 0보다 작았을 경우에 받은 숫자를 하나 증가시키고, countUp 함수 내부에서 countUp 함수를 하나 증가시킨 새로운 입력값으로 호출한다. 새로운 countUp함수에서는 증가된 값으로 다시 비교 연산을 실행하고, 10보다 작다면 다시 내부에서 함수를 호출한다. 이런 식으로 10까지 카운트 다운을 이어간다. 이렇게 내부에서 다시 같은 함수를 호출하는 방법을 재귀라고 말한다.
재귀를 배워야 하는 이유
- 재귀는 많은 솔루션에 다양하게 사용된다. 재귀적으로 작성된 솔루션들을 이해하기 위해서 필요하다.
- 가끔 반복을 사용하는것보다 재귀를 사용하는 것이 더 깔끔하기 때문이다.
재귀함수 작성의 핵심 구성요소
- 종료조건
- 재귀가 멈추는 순간 없으면 무한히 자신을 호출하며 문제가 생긴다. 루프의 중단점 같은 것.
function countUp(param){
var num = param;
//countUp의 중단점. 10이상이 되면 함수를 종료한다.
if(num >= 10){
console.log("done");
//return을 해서 끝내주어야 한다.
return;
}
console.log(num);
num++;
countUp(num);
}- 다른 입력값
- 함수를 호출할때마다 다른 입력값으로 호출해야한다.
function countUp(param){
var num = param;
if(num >= 10){
console.log("done");
return;
}
console.log(num);
//매번 이와같이 다른 입력값으로 함수를 호출한다.
num++;
countUp(num);
}호출스택
재귀코드를 호출할때 자바스크립트 내부에서는 무슨 일이 일어날까?
자바스크립트에서 호출된 함수들의 순서를 관리하는 데이터 구조가 있는데 이를 call stack(호출 스택) 이라고 한다. 함수를 호출하면 호출 스택 꼭대기에 쌓인다. 호출된 함수들은 호출된 함수는 다른 함수가 반환될때까지 기다린다. 그러다 위에 쌓인 함수가 return하거나 함수가 끝나면 컴파일러가 스택위의 함수를 제거한다. 그렇게 다음 함수에게 순서가 넘어간다.
function one(){
two();
three();
console.log("all done!");
return;
}
function two(){
return "call two";
}
function three(){
return "call three";
}
one();다음과 같이 one이라는 함수 내부에서 two와 three를 호출하는 함수를 실행했을 때, 과연 호출스택에서는 어떤 과정으로 일이 진행되는지를 살펴도록 하자.
먼저 one이 제일 먼저 호출된다.
그 다음 one 내부의 제일 첫줄에 있던 two가 호출된다. 이제 one은 two가 끝나고 값을 리턴할 때까지 대기상태가 된다.
이렇게 two가 값을 리턴한 뒤에 two를 컴파일러가 삭제한다. three도 마찬가지로 같은 과정으로 진행된다.
마지막으로 three까지 값을 return 하고 나면 one까지 끝나고 호출스택은 비워진다.
참고
