재귀의 사전적 의미는 다음과 같다.
원래의 자리로 되돌아가거나 되돌아옴.
즉, 다시 되돌아온다는 의미이다. 따라서 재귀 함수는 다시 되돌아오는 함수, 스스로를 다시 부르는 함수라고 정의할 수 있다. 간단한 재귀함수를 작성해보자면 다음과 같다.
function test() {
console.log('이건 재귀함수임')
test()
}재귀함수를 이용하면 반복적인 작업을 간단한 코드로 해결할 수 있다.
재귀를 활용한 문제 풀이
일반적으로 재귀를 통한 문제 풀이는 다음과 같은 단계로 나뉜다.
- 문제를 작게 쪼갠다.
- 1번에 이어 가장 작은 단위까지 문제를 쪼갠다.
- 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
다음 문제를 예시로 다음의 단계를 살펴보자.
숫자를 요소로 받는 배열을 입력받고 그 요소들의 곱을 리턴하는 함수를 재귀로 작성 (arrMul)
1. 문제를 작게 쪼갠다.
배열 [1, 2, 3, 4, 5]를 생각해보자. 1 x 2 x 3 x 4 x 5 의 답을 구해야 한다. (반복문을 사용해도 해결할 수 있으나 여기서는 재귀를 활용한다.) 이는 1 x ( 2 x 3 x 4 x 5) , 이는 다시 2 x ( 3 x 4 x 5), .... 계속해서 쪼갤 수 있을 것이다. 이를 표현하면 다음과 같다.
arrMul([1, 2, 3, 4, 5]) = 1 x arrMul([2, 3, 4, 5])
arrMul([2, 3, 4, 5]) = 2 x arrMul([3, 4, 5])
...2. 가장 작은 단위까지 문제를 쪼갠다.
arrMul([4, 5]) = 4x arrMul([5])
arrMul([5]) = 53. 가장 작은 단위의 문제를 해결한다.
arrMul([1, 2, 3, 4, 5]) = 1 x arrMul([2, 3, 4, 5]) = 1 x 120 = 120
arrMul([2, 3, 4, 5]) = 2 x arrMul([3, 4, 5]) = 2 x 60 = 120
arrMul([3, 4, 5]) = 3 x arrMul([4, 5]) = 3 x 20 = 60
arrMul([4, 5]) = 4 x arrMul([5]) = 4 x 5 = 20
arrMul([5]) = 5
위를 정리해 함수를 작성하면 다음과 같다.
function arrMul(arr) {
if(arr.length === 0) {
return 0
}
return arr.shift() * arrMul(arr)모든 재귀 함수는 반복문을 통해 다시 작성할 수 있다. 그러나 재귀를 사용하면 훨씬 더 간단하게 작성할 수 있다. 재귀는 다음과 같은 상황에서 자주 사용된다.
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
재귀적으로 사고하기
1. 재귀함수 입력값과 출력값 정의
arrMul : [number] => number
2. 문제의 경우의 수 나누기
arrMul([]) ← 입력값이 빈 배열인 경우
arrMul([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우
3. 간단한 문제부터 해결
arrMul([]) // 0 가장 간단한 문제
4. 어려운 문제 해결
arrMul([요소1, 요소2, ... , 요소n]) = 요소1 x arrMul([요소2, ... , 요소n])
5. 코드로 작성
function arrMul(arr) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive case : 그렇지 않은 경우
return 요소1 + arrMul([요소2, ... , 요소n]);
}페어와 함께 해결하고 실시간 세션에 참여했다면 좋았을 텐데... 코로나에 확진되면서 살짝 일정이 틀어졌다... 그래서 그런가...아직까지는 너무나도 어려운 개념이다. ㅜㅠㅜㅠㅜ
