S3) Unit 1. [자료구조/알고리즘] 재귀

📣  재귀의 개념

✔️ 재귀 : 원래의 자리로 되돌아가거나 되돌아옴.

➰ 재귀 함수 : 자기 자신을 호출하는 함수

 

📣  재귀로 문제 해결하기

1️⃣ 문제를 좀 더 작게 쪼갠다.

2️⃣ 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.

3️⃣ 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

 

✔️ 예시

➰ 배열 [1, 2, 3, 4, 5]의 합을 구하는 과정을 재귀로 풀어보자.

1. 문제를 작게 쪼개기

arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])

 

2. 문제를 가장 작은 단위로 쪼개기

➰ 더 이상 쪼갤 수 없는 상태까지 쪼갠다.

arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

 

3. 문제 해결하기

➰ 도달한 가장 작은 문제는 arrSum([]) 이므로, 0을 리턴해주면 된다.

➰ arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결된다.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

 

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

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

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

 

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

---

📣  재귀적으로 사고하기

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

➰ 문제를 가장 추상적으로, 가장 단순하게 정의한다.

➰ 함수의 입출력 값을 정하는 것은 그 첫 출발점이다.

 

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

➰ 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

➰ 입력값이나 문제의 순서와 크기를 고려한다.

 

3️⃣ 단순한 문제 해결하기

➰ 문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결한다 -> 재귀으 기초

➰ 재귀의 기초는 나중에 재귀의 탈출 조건을 구성한다.

 

4️⃣ 복잡한 문제 해결하기

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

 

5️⃣ 코드 구현하기

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

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

 

📣  예시

✔️ 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수

function fac(n) {
    if(n === 1) return 1;
    
    return n * fac(n-1);
}