[자료구조/알고리즘] 재귀

Recursive 재귀

Chapter1. 재귀의 이해

재귀의 개념

• 자기 자신을 호출하는 함수인 재귀(recursion) 함수
• ‘재귀’ 사전적 정의 : 원래의 자리로 되돌아가거나 되돌아옴.
• 반복적인 작업을 해야 하는 문제를 좀 더 간결한 코드로 풀어낼 수 있습니다.

 

재귀로 문제 해결하기

문제를 더 작게, 가장 작은 단위로 쪼개기 → 가장 작은 단위의 문제를 풀며 전체 문제를 해결

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

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

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

 

 

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

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

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

3. 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

 

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

 

Chapter2. 재귀의 활용

 

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

• 추상적으로, 가장 단순하게 정의하는 것
• 함수의 입출력 값을 정의
• 함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴 → • arrSum: [number] => number ← 입출력 값 정의

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

• 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인
• 입력값을 이 기준으로 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기
• 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면, 문제를 제대로 구분한 것
• 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 구분 력값이 빈 배열인 경우 (arrSum([ ]) VS 그렇지 않은 경우 (arrSum([요소1, 요소2, ... , 요소n])

3. 단순한 문제 해결하기

• 재귀의 기초 (base case) (재귀의 탈출 조건) 문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결 나중에 재귀 함수를 구현할 때, 재귀의 **탈출 조건(재귀 호출이 멈추는 조건)**을 구성한다. 탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다.

4. 복잡한 문제 해결하기

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
• arrSum: [number] => number
• arrSum([ ]) === 0
• arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
• 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있습니다.

5. 코드 구현하기

재귀 함수의 템플릿

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

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

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