재귀: (명사) 원래의 자리로 되돌아가거나 되돌아옴.
-네이버 국어사전
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!
재귀함수를 세분화한다면,
크게 세 부분으로 나눌 수 있다.
원치 않는 입력 값이 들어왔을 때 재귀가 계속해서 동작하는 것을 방지하는 안전장치.
if(원치 않는 입력 값이 들어온다면) {스탑!}
과 같다고 이해할수 있다.
재귀함수가 멈춰야 할 때를 정의해준다는 점에서는 종료 조건과 비슷하지만, 기반 조건은 재귀함수의 목적과 같은 역할을 한다.
if(이것이 일어난다면) {재귀 끝!}
과 같다고 이해할 수 있다.
함수가 자기자신을 다시 호출하는 부분으로 실제 반복적인 재귀활동이 일어나는 부분이다.
배열 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));
//120
factorialize(5);
의 반환값은 120
으로,
5! = 1 * 2 * 3 * 4 * 5 = 120
의 결과와 동일하다 😊
아래와 같이 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
로 다시 자기자신을 호출한다.
이 때, 모든 함수의 값이 반환되면서 원래 함수에게 최종적으로 값을 반환해준다.
*본 포스팅은 아래 사이트들을 참고 및 인용하여 작성되었습니다.
학습단계로 잘못된 정보가 있을 수 있습니다. 잘못된 부분에 대해 알려주시면 곧바로 정정하도록 하겠습니다 😊
https://codeburst.io/learn-and-understand-recursion-in-javascript-b588218e87ea
https://velog.io/@jakeseo_me/자바스크립트-개발자라면-알아야-할-33가지-개념-23-자바스크립트-자바스크립트-재귀Recursion-이해하기