[JavaScript] 재귀함수 기본개념 알기 (Recursive Function)

Dico·2020년 6월 26일
1

[JavaScript]

목록 보기
2/21
post-custom-banner

재귀함수(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));      
//120

factorialize(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-이해하기

profile
프린이의 코묻은 코드가 쌓이는 공간
post-custom-banner

0개의 댓글