재귀함수

재귀함수의 특징

재귀함수의 장점

• 코드 간결, 수정 용이
• 변수를 여러개 사용할 필요가없음

재귀함수의 단점

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

재귀함수의 템플릿

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