재귀의 개념
재귀란 무엇일까? 표준국어대사전에서는 다음과 같이 정의하고 있다.
재귀再歸 : 원래의 자리로 되돌아가거나 되돌아 옴.
재귀의 시각적 예시를 든다면 계속해서 원래의 상태로 돌아오는 아래 이미지와 같을 것이다.
재귀 함수란, 자기 자신을 호출하는 함수를 재귀 함수라고 한다.
재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.
재귀로 문제 해결하기
Q. 자연수로 이루어진 리스트배열을 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성해보자.
이론적으로 재귀로 문제를 해결하는 단계는 다음과 같다.
- 문제를 좀 더 작게 쪼갠다.
- 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
- 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
이 단계를 적용해서 arrSum 함수를 작성해보자.
배열은 [11,12,13,14,15] 로 하자.
1. 문제 작게 쪼개기
어떻게 하면 과정을 작게 쪼갤 수 있을까?
단순하게 생각해보면, 모든 배열의 합을 구하는 것 보다 가장 적은 수의 배열 값의 합을 구하는 것이 작은 문제일 것이다.
위 방식을 코드로 표현하자면
arrSum([11,12,13,14,15]) === 11 + arrSum([12,13,14,15])
// ...
arrSum([13,14,15]) === 13 + arrSum([14, 15])2. 문제를 가장 작은 단위로 쪼개기
위에서 쪼갠 방식을 반복해서 하다보면 더이상 쪼갤 수 없는 상태에 도달하게 된다.
arrSum([15]) === 15+ arrSum([])빈 배열을 받게 되면서 더이상 쪼갤 수 없게 되었다.
비로써 문제를 가장 작은 단위까지 쪼갰다고 할 수 있겠다.
3. 문제 해결하기
문제가 더 쪼개지지 않는다면 가장 작은 단위의 문제를 해결하자.
arrSum([]) === 0
arrSum([15]) === 15 + arrSum([]) === 15+0 === 15;
//...
arrSum([11,12,13,14,15]) === 11 + arrSum([12,13,14,15]) === 11 + 54 === 65위 단계를 반영해서 arrSum함수를 완성해보면 다음과 같다.
function arrSum(arr){
//빈 배열을 받았을 때 0을 리턴하는 조건문
//--> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if(arr.length === 0){
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자신을 호출)를 통해 문제를 작개 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}arrSum 함수는 계속 쪼개지다가 결국 쪼갤 수 없는 arrSum([]) 까지 함수가 호출된다.
arrSum([])은 조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다.
그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.
재귀는 언제 사용하는 게 좋은가?
재귀는 다음과 같은 상황에서 매우 적합하다
- 주어진 문제를 비슷한 구조의 더 작은 구조의 더작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
for (let l = 0; l < n; l++) {
for (let m = 0; m < n; m++) {
for (let n = 0; n < n; n++) {
for (let o = 0; o < n; o++) {
for (let p = 0; p < n; p++) {
// do something
someFunc(i, j, k, l, m, n, o, p);
}
}
}
}
}
}
}
}모든 재귀 함수는 반복문으로 표현할 수 있다.
그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용하는 코드가 더욱 간결하고 이해하기 쉽다.
재귀의 활용
재귀적으로 사고하기.
1. 재귀 함수의 입력값과 출력값 정의하기.
재귀적으로 사고하는 데 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것이다.
이 것은 그 출발점이며, 도달하고자 하는 목표를 정의하는 데 도움이 된다.
함수 arrSum의 경우 number타입을 요소로 갖는 배열을 입력받고, number타입을 리턴한다. 이를 더 간단하게 표기하면 다음과 같다
-
arrSum: [number] => numer<- 입출력값 정의2. 문제를 쪼개고 경우의 수를 나누기
다음으로는 주어진 문제를 어떻게 쪼갤 것인지 고민하자.
문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인하자.
일반적으로, 입력값을 이 기준으로 정한다.
이때 중요한 관점은 입력값이나 문제의 순서와 크기이다.
주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는데 도움이 된다.문제에서 주어진 입력값에 따라, 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
-
함수
arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.arrSum: [number] => numberarrSum([ ])<- 입력값이 빈 배열인 경우arrSum([요소,요소2,...요소n])<- 그렇지 않은 경우
3. 단순한 문제 해결하기
재귀의 기초(base case) = 문제를 구분한 다음 가장 해결하기 쉬운 문제부터 해결한다.
재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출조건(재귀 호출이 멈추는 조건)을 구성한다.
탈출조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다. 그렇다고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우에는 해결할 수 없게 된다. 그만큼 쪼갠다음 해결하는 것이 중요하다.
arrSum: [number] => numberarrSum([ ]) === 0<- 입력값이 빈 배열인 경우 : 해결arrSum([요소,요소2,...요소n])
4. 복잡한 문제 해결하기
- 길이가 1 이상인 배열이 함수
arrSum에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다. arrSum: [number] => numberarrSum([ ]) === 0arrSum([요소,요소2,...요소n])=== 요소1 + arrSum([요소2,...요소n])<- 그렇지 않은 경우: 해결- 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수
arrSum을 재귀적으로 구현할 수 있다.
5. 코드로 구현하지
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 더 작은 문제로 새롭게 정의된 문제
}