1. 재귀함수란?
재귀함수는 어떤 함수 안에서 다시 함수 자신을 호출하는 함수를 말한다.
2. 재귀함수의 사용 이유
재귀함수를 사용해서 만드는 함수는 거의 대부분 반복문을 이용해서 작성 가능하다. 그렇지만 반복문을 사용함에 있어 가독성이 떨어지는 경우 재귀함수를 사용하는것이 가독성이 좋아지는경우가 많다.
재귀함수 사용 이유에 대해서는 다음 두가지가 있다.
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
3. 재귀함수 예시
다음과 같은 문제 예시가 있다.
자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수
arrSum을 작성하세요.
arrSum([1,2,3,4,5]) 가 들어갔을때 결괏값으로 배열안의 숫자가 전부 더해진 15가 나와야 한다.
재귀함수 문제를 해결하는 방법으로는 3단계의 방법이 있다.
1. 문제를 좀 더 작게 쪼갠다.
2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
1. 문제를 좀 더 작게 쪼갠다
간단하게 생각해보면 배열 [1, 2, 3, 4, 5] 의 값을 구하는것 보다 [2, 3, 4, 5] 값을 구하는게 더 작은 문제가 될것이고 [3, 4, 5]가 더 작은 문제일 것이다.
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...2. 문제를 가장 작은 단위로 쪼갠다
위의 예시를 더이상 쪼갤 수 없는 상태에 도달하게 한다.
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])3. 문제 해결
문제가 더 쪼개지지 않게 되면, 가장 작은 단위의 문제를 해결한다. 위의 예시에서 더이상 쪼개지지 않는 부분은 arrSum([])으로 빈 배열의 합은 0으로 0을 리턴 해주면 된다. 이렇게 더이상 쪼갤수 없는 경우를 base case라 하며 재귀함수를 멈추는 코드로 필수적으로 들어가야 한다.
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5- base case의 값이 들어가면서 문제 전체가 해결되는 모습이다.
이를 코드로 나타낸다면 다음과 같다.
function arrSum (arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
//base case - 문제를 더이상 쪼갤 수 없는 경우
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
// recursive case : 그렇지 않은 경우
return arr.shift() + arrSum(arr)
}