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

키워드 : 재귀함수, base case, recursive case

---

재귀함수란?

자기 자신을 호출하는 함수

 

언제 사용하나?

반복문 대신 사용 가능.

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

 

반복문 vs 재귀함수

반복문 : 반복문을 여러번 중첩해서 사용해야할 경우 중첩횟수만큼 반복문을 써줘야 한다.

재귀함수 : 재귀함수는 반복되는 조건 한번만 써주고 탈출 조건만 만들어주면 내부에서 자기 자신을 계속적으로 호출하는 방식으로 문제 해결이 가능.

 

재귀적 사고 순서

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

ex)

• arrSum : [number] => number     // arrSum 함수의 경우, 입력값은 숫자 타입 배열, 출력값은 숫자 타입 리턴.

 

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

- 핵심 : 입력값, 문제의 순서 및 크기

ex)

• arrSum: [number] => number
• arrSum([ ]) ← 입력값이 빈 배열인 경우( 더 이상 쪼갤 수 없다)
• arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우 (더 쪼갤 수 있다)
  
  

3. 단순한 문제 해결하기 (Base case)

- 가장 해결하기 쉬운 문제부터 해결 => 재귀의 기초(base case) : 즉, 재귀의 탈출 조건

- 탈출 조건이 없으면 무한정으로 자기 자신을 호출.

- 문제를 최대한 작게 쪼개어 문제를 해결해야 함.

ex)

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

 

4. 복잡한 문제 해결하기 (Recursive case)

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

• 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 더 작은 문제로 새롭게 정의된 문제
}