재귀 함수
💡 함수가 함수 내부에서 자기 자신을 다시 호출해 작업을 실행하는 함수를 재귀함수라고 한다.
재귀 함수는 특정 분기 전까지 계속해서 자기를 호출해서 작업을 실행하므로 for, while과 같은 반목문 처럼 사용이 가능하다.
하지만, 반복을 멈출 특정 조건을 제대로 정해주지 않으면 Stack Overflow 에러가 발생하므로 주의할 필요가 있다.
재귀 함수를 사용할 때는 반드시 특정 조건을 잘 정해주도록 하자.
예제 코드
아래의 함수는 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 재귀함수를 통해 출력하는 함수이다.
function solution(n) {
function DFS (v) {
if(v === 0 ) return; //재귀함수가 멈추는 조건
else{
DFS(v-1); // 함수 반복 실행
console.log(v);
}
}
DFS(n); //DFS함수 실행
}
const N = 3;
solution(N); //solution함수 실행
//실행결과: 1 2 3실행 구조
위의 DFS 재귀함수가 실행되는 구조를 살펴보도록 하겠다.
solution함수에 인자 3을 넣고 실행하면 DFS(재귀)함수도 함께 실행되는데 DFS 함수는 v가 0이 될때까지 반복 호출된다.
DFS 함수가 호출 될 때마다 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 콜스택(call stack)에 저장된다.
DFS(3)을 호출하면 DFS(3-1)을 실행하여 DFS(2)를 호출하고 반환을 기다리게 된다.
동일하게 DFS(2), DFS(1)도 재귀가 멈추는 분기까지 마찬가지로 실행되며 콜스택에 쌓이게 된다.
그리고 DFS(1)에서 DFS(0)이 실행되면서 if(v === 0) 조건에서 반복 호출이 멈추고, 콜스택에 쌓인 역순으로 실행되면서 하나씩 콜스택에서 제거된다.
실행은 멈춘 시점 이후부터 다시 시작된다.
DFS(1) -> console.log(1)
DFS(2) -> console.log(2)
DFS(3) -> console.log(3)
따라서 실행 결과는 1 2 3이 된다.
재귀 함수가 실행된 후 콜스택에 저장되고 실행되는 순서를 직접 그리면서 따라가보니 재귀 함수 실행 구조에 대해 이해하기 좀 더 수월했다.
