[TIL-20210615] 재귀함수(Recursive function)

재귀함수(Recursive function)

재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며 그 반대도 가능하다. 재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있다.

// 반복문을 사용했을 경우
function factorial(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result = result * i;
   }
  
// 재귀함수를 사용했을 경우
function factorial(n) {
    if(n === 1) {
        return 1;
    }
    return n* factorial(n - 1);
} // 반복문 사용을 대신해서 재귀함수로 팩토리얼 함수가 구현 가능

재귀함수를 사용하는 경우

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

재귀적으로 사고하기

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

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

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

• 주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 쪼갤 기준을 정하고, 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다.

3. 단순한 문제 해결하기

• 문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결한다. 이를 base case라고 부른다. base case는 나중에 재귀함수를 구현할 때, 재귀 호출이 멈추는 탈출 조건을 구성한다.

4. 복잡한 문제 해결하기

• 쉬운 문제 해결 후, 남아있는 복잡한 경우를 해결한다.

5. 코드 구현하기

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