들어가기
이번 블로깅은 재귀에 대해 작성해 보려 한다. 개인적으로는 가장 어려운 개념이 아니였나 생각한다. 너무 어려워ㅠㅠㅠ 언제쯤 재귀함수도 자연스럽게 사용할 수 있게될까....
재귀란?
무엇이든 학습하기 전에 단어의 뜻을 먼저 알아본다. 이번에도 어김없이 뜻을 먼저 알아보자.
재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
네이버 사전에서는 재귀를 위와 같이 정의한다. 재귀 함수라고 함은 함수내부에서 자신을 다시 호출하는 함수를 말한다. 예를 들면 아래와 같다.
const func = () => {
console.log('hello!')
func()
}이렇게 특정 조건이 없다면 재귀 함수는 끝없이 반복하게 된다. 재귀는 다음과 같은 특성의 문제에 효과적이다.
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우를 예시 문제와 함께 조금 더 알아보자!
재귀의 활용
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수
arrSum을 작성하세요.
- 문제를 좀 더 작게 쪼갠다.
- 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
- 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
(가장 작은 문제 -> 다음으로 작은 문제 -> ... -> 전체 문제)
문제를 작게 쪼개기
단순하게 생각해보면, 배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다 [2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제일 것이다. 이를 코드로 표현해보면 아래와 같다.
const arrSum = () => { ... }
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...문제를 가장 작은 단위로 쪼개기
위에서 문제를 쪼갠 방식을 반복해서 문제를 계속해서 쪼개면 더이상 쪼갤 수 없는 상태에 도달하게 됩니다.
...
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])마지막에는 arrSum 이 빈 배열을 받게되면서 문제를 더이상 쪼갤 수 없게 되었다. 이는 문제를 가장 작은 단위로 쪼갰다는 것을 뜻한다.
문제 해결하기
위에서 도달한 가장 작은 문제는 arrSum([])이다. 빈 배열의 합은 0이므로, 0을 리턴해주면 된다. 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐진다.
rrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
...
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;이를 만족하는 함수를 작성해보면 다음과 같다.
const arrSum = (arr) => {
if (arr.length === 0) return 0
return arr.shift() + arrSum(arr)
}이로써 우리를 얻고자하는 답을 얻을 수 있다. 아래는 재귀함수를 일반화한 코드다.
function recursive(input1, input2, ...) {
// base case : 탈출 조건
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 반복 조건
return 더 작은 문제로 새롭게 정의된 문제
}마치며.
아직은 정확히 어떨때 반복문을 사용하고, 어떨때 재귀 함수를 사용해야 하는지 판단하기 어렵다. 또한, 익숙하지 않아서인가 적극적으로 활용하지 않는다. 훗날 멋진개발자가 된다면 재귀 함수를 반복문처럼 잘 다루게 되지 않을까 생각해본다. 오늘도 멋진개발자가 되기 위해 노력하는 아기개발자들 화이팅!!
