재귀함수(Recursive Function)란?
재귀: (명사) 원래의 자리로 되돌아가거나 되돌아옴.
-네이버 국어사전
Recursive: (adj.) involving doing or saying the same thing several times in order to produce a particular result or effect.
-Cambridge English Dictionary
'재귀' 혹은 'Recursive'의 사전적 의미는 위와 같다.
그렇다면 JavaScript에서는 어떤 의미일까?
재귀: 함수가 자기자신을 다시 호출하는 방식으로, 함수 내 하위의 문제들을 포함하고 있는 경우 문제해결에 이용된다.
Recursion: The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems.
-MDN
즉 재귀함수란, 함수 내에서 자기 자신을 다시 호출하는 함수를 말한다.
그렇지만
이렇게만으로는 감이 잘 안오늬...
예시와 함께 조금 더 자세히 알아보러 Let's go!
재귀함수의 형식
재귀함수를 세분화한다면,
크게 세 부분으로 나눌 수 있다.
1. 종료 조건 (A Termination Condition)
원치 않는 입력 값이 들어왔을 때 재귀가 계속해서 동작하는 것을 방지하는 안전장치.
if(원치 않는 입력 값이 들어온다면) {스탑!} 과 같다고 이해할수 있다.
2. 기본 조건 (A Base Case)
재귀함수가 멈춰야 할 때를 정의해준다는 점에서는 종료 조건과 비슷하지만, 기반 조건은 재귀함수의 목적과 같은 역할을 한다.
if(이것이 일어난다면) {재귀 끝!} 과 같다고 이해할 수 있다.
3. 재귀 (The Recursion)
함수가 자기자신을 다시 호출하는 부분으로 실제 반복적인 재귀활동이 일어나는 부분이다.
예제.
배열 arr의 첫 n개의 요소들을 더한 값을 찾는 재귀함수 sum(arr, n)이 있다. 아래 예제를 위 형식에 따라 나누어보면 다음과 같다.
function sum(arr, n) {
//종료 조건
if (n < 0) return 0;
//기본 조건
if (n === 0) return 0;
//재귀
return sum(arr, n - 1) + arr[n - 1];
}
sum([2, 3, 4, 5], 3)
//9재귀의 실행
재귀함수에서 가장 핵심이되는 재귀 부분의 실행흐름을 자세히 보자.
먼저 함수가 동작하면 if문을 넘어 재귀 부분으로 가게 된다. 이 때 sum(arr, 3-1)과 arr[3-1]이 더해진 결과를 반환한다.
return sum(arr, 2) + 4;
//배열 [2, 3, 4, 5]의 첫 2개 요소 + 4;sum(arr, 2)이 동작하며 if문을 다시 넘어 재귀가 일어난다. 이 때 sum(arr, 2-1)를 호출한다.
sum(arr, 1);
//배열 [2, 3, 4, 5]의 첫 1개 요소;그리고 다시 한번 sum(arr, 1) 이 실행되며 재귀가 일어나 sum(arr, 1-1)를 호출한다.
sum(arr, 0);
//배열 [2, 3, 4, 5]의 첫 0개 요소; sum(arr, 0)이 동작할 때, 기본 조건인 (n === 0)를 충족하게 되면서 함수는 0을 반환한다.
if (n === 0) return 0; 이와 같은 순서로 함수가 리턴을 마치게 되면, 가장 내부에 중첩된 함수부터 순차적으로 반환된다.
이처럼 sum([2, 3, 4, 5], 3)은 결국 2 + 3 + 4 와 동일해
값으로9를 반환하게 되는 것이다!👐
예제.
같은 원리로 흔히 우리가 알고있는 팩토리얼, n!을 재귀함수로 구현해본다면 다음과 같다.
function factorialize(num) {
//종료조건
if (num <= 0) return 1;
//재귀
return factorialize(num - 1) * num;
}
console.log(factorialize(5));
//120factorialize(5);의 반환값은 120으로,
5! = 1 * 2 * 3 * 4 * 5 = 120의 결과와 동일하다 😊
for 문 ➡️ 재귀함수
아래와 같이 for문으로 작성된 코드는 재귀함수로 재표현 될 수 있다.
즉, 함수가 자기 자신을 다시 불러올 수 있다면반복문을 사용하지 않아도 된다.
function sum(arr, n) {
var addedValue = 0;
for (var i = 0; i < n; i++) {
addedValue += arr[i];
}
return addedValue;
} sum(arr, n)은 sum(arr, n - 1) + arr[n - 1]로 breakdown할 수 있음을 주목해야한다❗️
function sum(arr, n) {
if (n <= 0) {
return 0;
} else {
return sum(arr, n - 1) + arr[n - 1];
}
} 중요한 것은, n <= 0와 같이 재귀함수는 항상 기본조건(Base Case)을 가져야한다는 것이다.
위 if-else문에서는 n <= 0인 경우 0을 반환한다.
n값이 더 큰 경우, n <= 0이 될 때까지 n - 1로 다시 자기자신을 호출한다.
이 때, 모든 함수의 값이 반환되면서 원래 함수에게 최종적으로 값을 반환해준다.
Reference
*본 포스팅은 아래 사이트들을 참고 및 인용하여 작성되었습니다.
학습단계로 잘못된 정보가 있을 수 있습니다. 잘못된 부분에 대해 알려주시면 곧바로 정정하도록 하겠습니다 😊
https://codeburst.io/learn-and-understand-recursion-in-javascript-b588218e87ea
https://velog.io/@jakeseo_me/자바스크립트-개발자라면-알아야-할-33가지-개념-23-자바스크립트-자바스크립트-재귀Recursion-이해하기
