[Java] 재귀

재귀의 개념

• 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다.
• 재귀 함수는 재귀적으로 구현된 함수를 의미하며, 재귀 호출은 함수 내에서 자기 자신을 호출하는 행위
• 재귀 함수에서 예외가 발생하지 않도록 중지 시킬 수 있는 조건을 기저 조건이라 한다.

재귀의 예시 이미지

재귀 함수 템플릿

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

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

재귀 코드

다음은 매개변수로 정수를 입력받으면 1부터 해당 정수 n까지의 합을 반복문을 통해 리턴해주는 메서드이다.

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int result = sum(n);
        System.out.println("1부터 " + n + "까지 더한 값은 : " + result);
    }
    // 1부터 range까지 더하는 메서드 - for 문
    static int sum (int range) {
        int total = 0;
        for (int i = 1; i <= range; i++){
            total += i;
        }
        return total;
    }
}

다음은 매개변수로 정수를 입력받으면 1부터 해당 정수 n까지의 합을 재귀 함수를 통해 리턴해주는 메서드이다.

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int result = sum(n);
        System.out.println("1부터 " + n + "까지 더한 값은 : " + result);
    }
    // 1부터 인자로 받은 n까지 더하는 메서드 - 재귀
    static int sum (int range) {
        // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
        if (range == 1) {return range;} // 무한 루프 방지 / 기저 조건
        // recursive Case 
        return range + sum(range - 1);
    }
}

위의 재귀 코드 동작 방식

재귀 함수의 스택 오버 플로우

• 재귀 함수란 자기 자신을 호출하는 것이다.
• 여기서 자기 자신을 무한정으로 호출하게 되면 어떻게 될까?
• 재귀 함수도 함수의 형태이므로 호출될 때마다 복사본을 만들어 새 스택 프레임 메모리 공간을 할당받는다.
• 만약 무한정으로 자기 자신을 호출하게 되면 언젠가 스택 영역이 가득 차게 되어 더 이상 스택 영역을 사용할 수 없어 스택 오버 플로우(Stack Overflow)가 발생하게 된다. -> 기저 조건의 필요 이유

재귀의 스택 오버 플로우

재귀 함수의 장점

• 반복문을 대신할 수 있기 때문에 코드가 간결해지며, 수정이 용이하다.
• 변수를 여러 개 사용할 필요가 없다.

재귀 함수의 단점

• 코드의 흐름을 직관적으로 파악하기 어렵다.
• 반복문과 비교하여 메모리를 더 많이 사용한다.
• 재귀 호출이 종료된 이후 복귀를 위한 컨텍스트 스위치 비용이 발생한다.

재귀 함수의 조건

• 문제의 크기를 작은 단위까지 쪼갤 수 있어야 한다.
• 재귀 호출이 종료될 수 있는 조건이 존재해야 한다. (기저 조건)