코드스테이츠 25일차
2020년의 마지막 날이 되었다.
혹시나 이 글을 보고있는 분이 계시다면
내년엔 하시는일이 모두 잘됐으면 하는 바램이다.
마지막 날이라 꼭 12시까지 안자야겠다는 생각을 하고있지만.
사실 어젯밤에 잠자리에 누운게 11시 반쯤이었는데
새벽에 갑자기 배가 아파서 잠을 제대로 못잤다.
침대에서 마지막으로 시계를 본 시간이 아침 6시 반쯤이었는데
그렇게 한시간 반정도 잠을자고 지금까지 깨어있는것이다.
그래도 마지막날인대 12시까지 버텨야겠다.
새로 배운 것들
재귀함수
함수를 재사용하는 것을 말하는 것이다.
function sumTo(num) {
if(num <= 1) {
return num
}
return num + sumTo(num - 1)
}위 함수는 어떤 수를 입력받아
그 수에 다음 수를 더한 값을 리턴하는 함수이다.
대략 이런 모습인 것이다.
sumTo(4) = 1 + 2 + 3 + 4 = 10재귀함수가 구동되는 과정을 다시 살펴보면 이런 모습이다.
function sumTo(4) {
if(4 <= 1) {
return 4
}
return 4 + sumTo(3) { // 4 + 6 = 10
if(3 <= 1) {
return 3
}
return 3 + sumTo(2) { // 3 + 3 = 6
if(2 <= 1) {
return 2
}
return 2 + sumTo(1) { // 2 + 1 = 3
if(1 <= 1) {
return 1 // sumTo(1) = 1
}
} 재귀함수를 통해 계속 같은 함수를 호출하는 것을 알 수 있다.
이렇게 호출된 함수는 다음 값이 계산될 때까지 호출이 대기되는
일종의 비동기 처리를 하는셈이다.
또한 재귀함수를 이용하면 반복문을 이용하는 것보다.
더욱 짧은 코드를 짤 수 있게된다.
// 반복문을 사용해 작성한 함수
function factorial(n) {
let result = 1;
for (let 1 = n; i > 0; i--) {
result = result * i;
}
return result;
}// 재귀함수를 사용해 작성한 함수
function factorial(n) {
if(n === 0) {
return 1;
}
return n * factorial(n - 1);
}두 코드를 비교해보면 같은일을 하는 함수이지만
반복문을 이용한 함수는 뭔가 타이핑한것이 많아보이는 차이가 있다.
이런 재귀함수는 어떻게 작성해야되는걸까?
재귀 함수 사용법
어떤 문제가 주어졌을 때 무엇을 입력받고 어떻게 출력할지
정하는것부터 시작하는것이 좋다.
예를들어 숫자로 구성된 배열을 입력받아 그 요소 하나하나를
다시 숫자로 리턴해야된다면 어떻게 표현할 수 있을까?
arrSum: [number] -> number
아마 이런식으로 표현할 수 있을 것이다.
이렇게 출력해야한다면 다음은 어떤기준으로
문제를 해결할 것인지 생각해봐야된다.
이 때 중요한 관점은 순서와 크기이다.
주어진 입력값을 기준으로 구분할 수 있거나,
순서를 명확하게 정할 수 있는지 살펴보자.
arrSum의 경우 입력값인 배열의 크기에 따라 구분할 수 있을 것이다.
arrSum([1, 2, 3, 4])과 arrSum([2, 3, 4])의
크기를 구하는 방법은 동일하다는 것을 알고있다.
그렇다면 몇가지 조건을 걸 수 있을 것이다.
arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다.arrSum: [number] -> numberarrSum([])arrSum([e1, e2, ..., en])
이렇게 문제를 나눈 후 가장 쉬운 문제부터 해결해보자
이렇게 해결하는 문제를 재귀의 기초라고 부른다.
재귀의 기초는 재귀함수 구현 시 재귀의 탈출 조건이 되기도 한다.
arrSum은 입력값이 빈 배열인 경우arrSum = 0이다arrSum: [number] -> numberarrSum([])arrSum([e1, e2, ..., en])
이제 좀더 복잡한 문제를 해결해나가보자
-
arrSum이 길이가 1 이상인 배열을 입력받은 경우
맨 앞의 요소를 따로 구하고
(배열의 맨 앞 요소이기때문에 head라고 이름을 붙인다.),
나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여
얻은 결과를head에 더한다. -
arrSum: [number] -> number
arrSum([])
arrSum([e1, e2, ..., en]) = e1 + arrSum([e2, ..., en]) -
배열이 있을 때
head와 나머지 부분(tail)을 구분하는 방법만 안다면arrSum을 해결할 수 있다.
이렇게 쪼갠 문제를 코드로 구현해보면 아래와 같다.
function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}이렇게 구성된 방식을 재귀의 템플릿이라고 볼 수 있다.
이를 활용해 다양한 문제를 재귀함수로 해결하는데에 연습해보자
