[자료구조] 재귀 함수

재귀함수

 자기 자신을 끊임없이 호출하면서 같은 코드가 반복 실행되는 함수

• 장점
  • 불필요하게 여러 반복문을 사용하지 않기때문에 코드가 간결해진다.
  • 변수를 여러개 사용할 필요가 없다.
• 단점
  • 코드의 흐름을 직관적으로 파악하기 어렵다
  • 반복 호출하면서 지역변수, 매개변수, 반환값을 process stack에 저장하게 되고 결국 반복문에 비해 메모리를 더 많이 사용하게 된다.
  • 메서드 종료이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.
• 사용 조건
  •  문제의 크기를 순차적으로 작은 단위로 쪼갤 수 있어야 한다.
  • 재귀 호출이 종료되는 시점이 있어야 한다.
• 적합한 상황
  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우
  • 변경 가능한 상태(mutable state)를 제거하여 프로그램 오류 발생 가능성을 줄이는 경우

 

 재귀적으로 사고하는 법

1. 재귀 함수 입력, 출력값 정의
   • 어떤 타입을 입력받고, 어떤 타입을 리턴하는지
2. 문제를 쪼개고 경우의 수 나누기
3. 단순한 문제 해결
   • 문제를 여러 경우로 구분한다음 재귀의 기초로서 가장 해결하기 단순한 문제부터 해결한다.  재귀의 기초는 재귀의  탈출 조건을 구성한다.
4. 복잡한 문제 해결
5. 코드 구현
   • 코드는 두 가지 조건으로 이루어진다.
   • 재귀 탈출 조건 - 단순한 문제 해결하기 영역
   • 재귀 목적 - 복잡한 문제 해결하기 영역

public type recursive(input1, input2, ...) {
// 재귀 탈출 조건 구성(재귀의 기초)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
 
  /*
  * 복잡한 문제 해결하기 영역(재귀의 목적)
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}