[자료구조/알고리즘] 재귀 함수 작성 가이드

0. 학습목표

1) 재귀로 문제를 해결하는 방법을 이해한다. 2) 재귀의 기초(base case)와 탈출 조건에 대해 이해한다. 3) 재귀함수를 base case와 recursive case로 나누어 작성할 수 있다.

1. 재귀 함수 작성 방법

※ 예제 : 팩토리얼(factorial) 값을 계산하는 함수 'factorial'을 작성

n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다. ex1) 5! = 5 * 4 * 3 * 2 * 1 ex2) num! = num * num-1 * ... * 2 * 1

1) 재귀함수의 입력값과 출력값을 정의합니다.

우리가 작성할 함수 factorial의 경우 number 타입의 정수(num >=0)를 입력으로 받고, number 타입을 리턴합니다. 

factorial: number => number  // 입출력값 정의

2) 문제를 쪼개고 경우의 수를 나눕니다.

주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나,

순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다.

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

일반적으로 입력값을 쪼개기의 기준으로 정합니다.

// 주어진 입력값에 따라, 경우의 수를 나눕니다
factorial(5) = 5! = 5 * 4 * 3 * 3 * 1 = 5 * ( 4 * 3 * 2 * 1) = 5 * 4!
factorial(4) = 4! = 4 * 3 * 2 * 1 = 4 * ( 3 * 2 * 1) = 4 * 3!
// factorial(5)를 구하는 방법과 factorial(4)를 구하는 방법이 동일하므로 이 구분은 적절하다고 판단할 수 있습니다.

함수 factorial의 동작은 인자로 전달 받은 값이 0인 경우와 그렇지 않은 경우로 나눌 수 있습니다.
각각의 경우는 다른 방식으로 처리해야하며
이때, 인자로 전달 받는 값이 0이라는 특수한 경우 또한 재귀의 탈출 조건인 base case가 됩니다.

factorial(0) === 1  // 예외 처리. 이 또한 base case에 포함된다.

3) 재귀의 탈출 조건 (=재귀호출이 멈추는 조건)인 Base case를 구성합니다.

탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 됩니다. 

그렇다고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 됩니다. 

그렇게 때문에 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요합니다.

factorial(5) = 5! = 5 * 4 * 3 * 3 * 1 = 5 * ( 4 * 3 * 2 * 1) = 5 * 4!
factorial(4) = 4! = 4 * 3 * 2 * 1 = 4 * ( 3 * 2 * 1) = 4 * 3!
factorial(3) = 3! = 3 * 2 * 1 = 3 * ( 2 * 1) = 3 * 2!
factorial(2) = 2! = 2 * 1 = 2 * (1) = 2 * 1!
factorial(1) = 1	// 더이상 쪼갤 수 없는 가장 작은 단위. 이것을 base case로 설정합니다.

함수 factorial을 더이상 쪼갤 수 없는 경우는 입력값이 1인 경우이고, 이때 factorial(1)의 리턴값은 1입니다.

또다른 base case인 factorial(0)의 리턴값 또한 1이므로 base case에 대한 처리 구문을 아래와 같이 작성할 수 있습니다.

if (입력값 <= 1) {
    return 1;
}

4) 재귀 부분인 Recursive case를 작성합니다.

입력값 * factorial(입력값 - 1);

5) 완성

function factorial(num) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우. 재귀함수의 탈출 조건이 된다.
  if (num <= 1) {
    return 1;
  }

  // recursive case : 그렇지 않은 경우
  return num * factorial(num - 1);
}

2. 재귀함수 기본 템플릿

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

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

3. 학습 후 내린 주관적 결론

1) 문제를 동일한 방식으로 쪼개기 : 쪼개는 방식이 recursive case가 된다. 2) 더이상 쪼개지지 않으면 : 가장 작은 단위가 바로 재귀 함수의 탈출 조건인 base case. 3) 재귀 함수는 : 베이스 케이스의 값으로부터 시작해 함수 실행의 결과값을 연쇄적으로 리턴하며 최종 결과값을 얻는 구조.

1) 문제를 많이 풀어보는 게 답 2) 쪼개지는 구조를 직접 그려보는 것도 이해에 도움이 된다. (트리 구조)