재귀의 이해
재귀란 원래의 자리로 되돌아가거나 되돌아옴 을 뜻한다.
코드로 표현한다면
function recursion () {
console.log("This is")
console.log("recursion!")
recursion()
}이렇게 표현할 수 있는데 이 함수를 호출하면
무한대의 This is 와 recursion!이 나타난다.
이처럼 자기 자신을 호출하는 함수를 재귀함수라고 하며 반복적인 작업을 해야하는 문제를 더 간결하게 풀어낼 수 있다.
재귀로 문제 해결하기
코플릿 문제의 예시
문제
배열 [1, 2, 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])
...[1, 2, 3, 4, 5]의 합을 구하는것 보다 [2, 3, 4, 5]의 합을 구하는것이 더 작은 문제이며 [3, 4, 5]의 합을 구하는것은 더욱 작은 문제일것이다.
- 문제를 가장 작은 단위로 쪼개기
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])마지막에는 빈배열을 받게되면서 더이상 쪼갤 수 없다.
- 문제 해결하기
arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되며 문제 전체가 해결된다.
모든 재귀 함수는 반복문으로 표현할 수 있으나 재귀를 적용할 수 있는 대부분의 경우에는 재귀를 적용한 코드가 더욱 간결하고 이해가 쉽다.
이외에도 재귀는 알고리즘 문제의 많은 부분을 차지하므로 다양한 과제와 기업의 입사 시험, 직무면접에서 활용될 수 있으므로 중요하다.
재귀의 활용
- 재귀 함수의 입력값과 출력값 정의하기
재귀적인 사고를 하는데에 가장 먼저 할 일은 문제를 가장 추상적으로 또는 가장 단순한게 정의하는것이다. 함수의 입출력값을 정의하는것이 그 출발점이다.
함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다.
arrSum: [number] => number ← 입출력값 정의
- 문제를 쪼개고 경우의 수를 나누기
주어민 문제를 어떻게 쪼갤 것인지 고민한다. 기준에 따라 문제를 더 큰경우, 작은 경우로 구분할 수 있는지 확인하고 이 기준은 일반적으로 입력값을 기준으로 한다. 이때 중요한 관점은 입력값이나 문제의 순서, 크기이다.
함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 으며 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눕니다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.
함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있으며 각각의 경우는 다른 방식으로 처리해야 한다.
arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우
- 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음엔 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 부르며 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 되고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 된다. 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요하다.
함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은
arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n])
-
복잡한 문제 해결하기
길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다. -
코드 구현하기
function arrSum(arr) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive case : 그렇지 않은 경우
return 요소1 + arrSum([요소2, ... , 요소n]);
}일반적인 재귀 함수의 템플릿
function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
}