재귀함수

• 자기 자신을 호출하는 함수

• 재귀함수의 장점

  • 불필요하게 여러개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고, 수정이 용이하다.
  • 변수를 여러개 사용할 필요가 없다.

• 재귀함수의 단점

  • 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.
  • 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 되어 반복문에 비해 메모리를 더 많이 사용하게 된다.
  • 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.

• 재귀는 다음과 같은 상황에서 적합하다.

  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
  • 변수 사용을 줄여 mutable state (변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

재귀적 사고

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제 해결하기
4. 복잡한 문제 해결하기
5. 코드 구현하기

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

public type recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}