[SEB BE] Section 2. 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값을 가장 단순하게 정의한다.

int arrSum(int[] arr){} 의 경우 가장 단순하게 쪼갠다면 이런 형식이 될것이다.

arrSum:[int] => int

2. 입력값을 기준으로 문제를 구분한다.

일반적으로 입력값을 기준으로 문제를 구분하지만 문제푸는 순서나 크기를 기준으로 문제를 구분할 수 있다. 만일 이 모든것이 관계없이 같다면 문제를 제대로 구분한 것이라고 볼 수 있다.

int arrSum(int[] arr){

}

앞의 arrSum()를 입력값을 기준으로 문제를 구분하자면,
입력값이 빈 배열과 아닌 경우로 나눌 수 있다.

arrSum: [number] => arrSum(new int[]{}) / arrSum(new int []{요소...]}

3. 제일 해결하기 <쉬운문제부터 해결한다.

문제를 구분한 다음에는 가장 해결하기 쉬운분제부터 해결한다. 이것은 재귀함수를 구현할 때 탈출조건을 구성하는 재귀기초이다.

• 함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우다.
• 이때 arrSum(new int[]{}) 의 리턴값은 0이다.

  arrSum: [number] => arrSum(new int[]{}) = 0
  / arrSum(new int[]{e1, e2, ... , en]}

4. 남아있는 복잡한 문제 해결하기

남아있는 복잡한 문제의 head와 tail부분으로 나눈다.
여기서는 head는 배열의 맨 앞에 있는 숫자이며 tail은 배열의 첫 요소만 제거된 나머지 배열을 의미 한다.

head에 배열의 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고 이를 해결한 결과를 head에 더한다.

arrSum: [number] => numberarrSum(new int[]{}) = 0 /
arrSum([e1, e2, ... , en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}

5. 코드구현

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