Week 4-2 : 재귀적으로 생각하기
TIL List
- 재귀의 이해
- 재귀적 사고 연습하기
1) 재귀?
국어사전에 따르면 재귀란 "원래의 자리로 되돌아가거나 되돌아옴." 이라고 적혀있다.
따라서 재귀 함수란, 자기 자신을 호출(리턴)하는 형태의 함수다. 반복되는 형태라는 점에서 반복문 (For, Whlie) 과 같다고 할 수 있다.
특정 배열의 요소의 합을 구하는 코드를 짜본다고 가정해보자.
반복문에 대해 충분히 이해했다면 별 문제 없이 다음과 같이 코드를 짤 수 있을 것이다.
let arr = [1,2,3,4,5];
function getArrSum (arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum = sum + arr[i]
}
return sum; // getArrSum(arr) === 15 -> true
}위와 같이 반복문을 통해 arr 의 요소의 합을 쉽게 구할 수 있다.
이번엔 위 문제를 재귀적 사고 로 바라봐보자.
2) 재귀적 사고 연습하기
- arr의 요소인 [1,2,3,4,5] 의 총합을 구해야 하므로 총합은 1 + 2 + 3 + 4 + 5 가 돼야한다.
- 한 번에 계산하는건 복잡하니 하나씩 접근해보자. 2 + 3 + 4 + 5 의 합을 먼저 구해본다.
- 이것도 복잡하니 3 + 4 + 5 의 합을 구해본다.
- 좀 더 간결하게 먼저 4 + 5 의 합을 구해본다.
위 문제를 재귀적 사고 를 통해 코드로 작성한다면 다음과 같을 것이다.
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
arrSum([]) = 0;문제를 잘개 잘개 쪼개서 하나하나씩 해결해 나가는 과정을 볼 수 있다.
이와 같이 재귀적 사고 는 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀적 사고(recursion)라고 한다.
사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능하지만, 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽다.
하지만 위 코드에는 문제점이 있다. 바로 탈출 조건이 명시돼있지 않다는 것이다.
따라서 저 코드는 자신이 언제까지 이 짓을 반복해야하는지도 모른채 끝 없는 반복을 거치다가 결국 MAXIMUM CALL STACK 이란 처절한 결과를 나타낼 것이다.
여기서 알 수 있는건 재귀 함수 또한 반복문과 같이 탈출 조건을 반드시 명시해줘야 한다는 점이다.
따라서 탈출조건은 다음과 같이 설정할 수 있다.
1. 만약, arr의 길이가 0일 경우, 즉 빈 배열일 경우 0 을 리턴한다.
2. 1번을 이용해 arr의 요소를 모두 돌아서 arr의 요소가 더 이상 존재하지 않을 때까지 반복한다.
3. 그 외의 경우는 첫 요소 arr[0] 에 나머지 배열을 모두 더한다.이제 이것을 코드로 작성해본다면 다음과 같을 것이다.
let arr = [1,2,3,4,5];
function arrSum(arr) {
if (arr.length === 0) { // 탈출 조건
return 0;
}
const head = arr[0];
const tail = arr.slice(1);
return head + arrSum(tail)
}
arrSum(arr) // 15위를 봐도 저 코드가 어떻게 작동되는지 이해가 잘 안될 수 있다. 아래는 위 코드가 작동되는 과정이다.
head = [1] tail = [2,3,4,5] // 처음 함수 실행 시 head, tail 의 값
return [1] + arrSum([2,3,4,5])
head = [2] tail = [3,4,5] // return 을 통해 다시 실행된 함수의 head, tail 값
return [2] + arrSum([3,4,5])
head = [3] tail = [4,5] // return 을 통해 다시 실행된 함수의 head, tail 값
return [3] + arrSum([4,5])
head = [4] tail = [5] // return 을 통해 다시 실행된 함수의 head, tail 값
return [4] + arrSum([5])
head = [5] tail = [] // return 을 통해 다시 실행된 함수의 head, tail 값
return [5] + arrSum([0])
// tail이 빈 배열, 즉 입력받은 arr이 빈 배열이므로 조건문에 따라 0을 리턴한다.
// arrSum 에 0의 값을 받았으므로 역순으로 다시 올라가면서 합을 구한다.
5 + 0 = 5 // return [5] + arrSum([0])
5 + 4 = 9 // return [4] + arrSum([5])
9 + 3 = 12 // return [3] + arrSum([4,5])
12 + 2 = 14 // return [2] + arrSum([3,4,5])
14 + 1 = 15 // return [1] + arrSum([2,3,4,5])변수 head 를 기준으로 tail 의 요소 하나하나를 더하는 것을 볼 수 있다.
