(S2W1) TIL 23일차 220302 (자료구조/알고리즘 기초 - 재귀)

오늘의 학습 목표

1. 아침 8시에 기상해 스터디원들과 함께 Toy 알고리즘 문제 1번을 잘 이해하고 풀어본다. (블로깅)

2. 오늘 배울 재귀에대해 남에게 설명할 수 있을만큼 이해하고, 블로깅한다.

3. 페어 스프린트를 진행할 때 스프린트를 잘 이해하고, 이해가 안되는 부분을 블로깅한다.

4. 저녁시간에 오늘 풀어본 Toy 알고리즘 문제를 한번 더 풀어본다.

5. 내일 학습할 내용, Toy 알고리즘 문제를 훑어보며 준비한다.

 

학습 내용

재귀(recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 자기언급과도 관련된 재귀는 언어학에서 논리학에 이르기까지 다양한 분야에서 연구되는 주제로, 특히 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다.

 

재귀는 언제 사용하는게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

 

부가 설명

모든 재귀 함수는 반복문(while문, for문)으로 표현할 수 있습니다.

그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.

재귀는 알고리즘 문제의 많은 부분을 차지합니다.

다양한 스프린트와 기업의 입사 시험(코딩, 알고리즘 테스트)에서 직무면접에서 활용되기에 기초를 탄탄히 다집시다.

 

재귀적 사고 연습하기

재귀는 자전거 타는 것과 비슷합니다. 다른사람이 타는 것을 옆에서 지켜볼땐 꽤 쉬워보이지만, 내가 배우려 하면 생각보다 잘 안되듯이 계속 시도하고 연습하는 수 밖에 없습니다. 자연스러워질 때까지 연습합시다!

 

재귀적으로 사고하기 Guide

1. 재귀 함수의 입력값과 출력값 정의하기

재귀적으로 사고하는 데에 먼저 해야 할 일은 문제를 가장 단순하게 정의하는 것입니다.

함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴합니다.

arrSum: [number] => number // 간단하게 정의한 arrSum

2. 문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤지 고민해, 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다. 일반적인 경우, 입력값으로 이 기준을 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다. 주어진 입력값 또는 문제상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는데에 도움이 됩니다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 같다면 제대로 구분한 것입니다.

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음은 가장 해결하기 쉬운 문제부터 해결합니다. (재귀의 기초(base case)라고 부릅니다)

재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.

4. 복잡한 문제 해결하기

남아있는 복잡한 문제를 해결합니다.

5. 코드 구현하기

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

// 일반적인 재귀 함수의 탬플릿
function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

 

 

 

오늘의 회고

오늘 나름 열심히 했지만 생각보다 많이 어렵다고 느꼈고 코플릿 13, 14, 15번을 이번 주말에 좀더 봐야겠다고 생각했습니다. 스스로 많이 부족하다고 느낀 하루였고, 재귀함수 연습을 꾸준히 해야할 것 같습니다.