(SEB_FE) Section3 Unit1 재귀

PYM·2023년 4월 11일

(SEB_FE) SECTION3

목록 보기

1/22

재귀의 의미에 대해서 이해한다.
JavaScript에서 재귀 호출을 할 수 있다.
재귀를 언제 사용해야 하는지 이해한다.
재귀로 문제를 해결하는 방법을 이해한다.
재귀의 기초(base case)와 탈출 조건에 대해 이해한다.
재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

🍎재귀란?

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

// 간단한 재귀 함수 예시 
function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

recursion 함수를 호출하면, 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행된다.

이 recursion 함수처럼 자기 자신을 호출하는 함수를 재귀 함수라고 한다.

재귀 함수를 잘 활용하면 반복적인 작업을 해야 하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다!

🍒어떤 상황에서 재귀를 사용할까?

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다.
그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

🍒일반적인 재귀 함수의 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

🍎재귀적으로 사고하기

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

재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것!

예시로 자연수로 이루어진 배열을 입력받고, 리스트의 합을 리턴하는 함수 arrSum는

입출력 값 정의 : arrSum: [number] => number

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

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

문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인. 일반적으로, 입력값을 이 기준으로 정한다.

이때 중요한 관점은 입력값이나 문제의 순서와 크기!!
주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.

그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면, 문제를 제대로 구분한 것!

예시로 살펴보자.

함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다.
그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다.
일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.
- arrSum: [number] => number
  입력값이 빈 배열인 경우 ➡ arrSum([ ])
  그렇지 않은 경우 ➡ arrSum([요소1, 요소2, ... , 요소n])

🍒3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다.
이를 재귀의 기초(base case)라고 부른다.

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

🚨탈출 조건이란?🚨
탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다!
즉, 무한 루프에 빠지게 되는 것!

BUT! 문제를 덜 쪼갠 상태로 탈출 조건을 세우면, 문제를 제대로 해결할 수 없다. 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요

예시로 살펴보자

함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0이다.
- arrSum: [number] => number
  arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
  arrSum([요소1, 요소2, ... , 요소n])

🍒4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.