재귀

알고리즘

재귀 함수

재귀 함수의 이해

사전적 의미로 재귀는 원래의 자리로 되돌아가거나 되돌아오는 것을 의미한다.
재귀 함수는 자기 자신을 호출하는 함수를 일컬으며, 반복적인 작업을 해야하는 문제를 간결한 코드로 풀어낼 수 있다.

재귀 함수의 장점

• 여러 반복문을 사용하지 않아 코드가 간결하고 수정에 용이함
• 여러 변수를 사용할 필요가 없음

재귀 함수의 단점

• 코드의 흐름을 직관적으로 파악하기 어려움
• 반복문에 비해 많은 메모리 사용
• 메서드를 호출하고 종료된 후에 복귀를 위한 컨텍스트 스위칭 비용 발생

재귀 함수의 사용 조건

• 문제의 크기를 점점 작은 단위로 나눌 수 있어야 함
• 재귀 호출이 종료되는 시점이 존재해야 함

재귀 함수의 동작 원리

1. 재귀 함수의 입출력 값을 정의한다

// int타입을 요소로 갖는 배열을 입력 받고, int 타입을 리턴
arrSum: [int] -> int

2. 문제를 쪼개고 경우의 수를 나눈다.

// 입력값이나 문제의 순서와 크기에 따라 구분
// 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 쪼갤 수 있는 경우로 분류
arrSum: [number] => arrSum(new int[]{}) / arrSum(new int[]{n1, n2, ... , nn})

3. 단순한 문제를 해결한다.

// 구분된 문제 중 해결하기 가장 쉬운 문제부터 해결(재귀의 기초)
// 재귀의 기초는 재귀 함수를 구현 시 재귀의 탈출 조건을 구성
arrSum: [number] => arrSum(new int[]{}) = 0 / arrSum(new int[]{n1, n2, ... , nn})

4. 복잡한 문제를 해결한다.

// 길이가 1 이상인 배열이 함수 arrSum에 입력된 경우
arrSum: [number] => arrSum(new int[]{}) = 0 / arrSum(new int[]{n1, n2, ... , nn}) = arrSum(new int[]{n1} + arrSum(new int[]{n2, ..., nn}))

5. 코드를 구현한다.

public int arrSum() {
  // 재귀의 기초 : 문제를 더 이상 쪼갤 수 없는 경우
  if(arr.length == 0) { // 배열의 길이가 0인 경우
 return 0;
  }
  // 문제를 쪼갤 수 있는 경우
  // head : 배열의 첫 요소
  // tail : 배열의 첫 요소만 제거된 배열
  return head + arrSum(tail);
}