[JAVA] 재귀 (Recursion)- Chapter 12

재귀 (Recursion)는 문제를 더 작은 단위로 나누어 해결하기 위한 접근 방식이다.

자기 자신을 호출하며 변경된 인수를 사용하여 기본 조건에 도달할 때 까지 수행된다.

 

기본 조건

실제 값을 반환하고 재귀 호출을 종료하는 조건이다.

 

재귀 호출

기본 조건에 의해 종료될 때 까지 자기 자신을 호출 한다.

 

 

재귀 호출은 메서드 바디에서의 호출 위치에 따라 두가지로 나뉠 수 있다.

 

머리 재귀

재귀 호출이 함수의 시작 부분에 위치한다.

결괏값을 반환하기 전에 재귀 호출이 이루어져 런타임이 반환될 때 까지 최종 결괏값을 확인 할 수 없다.

머리 재귀는 함수가 자신을 호출한 후에 나머지 작업을 수행해야 하므로 호출 스택이 커질 수 있다.

 

public class HeadRecursion {
    public static int headRecursionSum(int n) {
        if (n == 0) {
            return 0;
        } else {
            return n + headRecursionSum(n - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(headRecursionSum(5)); // 출력: 15 (1+2+3+4+5)
    }
}

 

 

꼬리 재귀

재귀 호출이 함수의 마지막 작업으로 위치한다.

각 단계의 문제를 먼저 해결한 후 그 결과를 다음 재귀 호출로 전달한다.

꼬리 재귀는 컴파일러나 인터프리터가 최적화를 통해 호출 스택을 재사용할 수 있어 메모리 효율성이 높다.

 

public class TailRecursion {
    public static int tailRecursionSum(int n, int acc) {
        if (n == 0) {
            return acc;
        } else {
            return tailRecursionSum(n - 1, acc + n);
        }
    }

    public static void main(String[] args) {
        System.out.println(tailRecursionSum(5, 0)); // 출력: 15 (1+2+3+4+5)
    }
}

 

재귀 vs 반복

자바는 꼬리 호출 최적화를 지원하지 않기 때문에 오버헤드를 고려해야 한다.

반복에 비해 실행 시간을 느리게 할 뿐만 아니라, 호출 스택이 너무 깊을 경우 stackOverflowError의 위험도 있다.

반면 재귀는 추상적인 문제를 해결되는데 선호되며, 프로그래머의 생산성을 향상시킬 수 있다.

문제와 코드의 환경에 따라 재귀와 반복 중 선택하여 사용하도록 하자.

 

*꼬리 호출 최적화 (Tail Call Optimization, TCO)

재귀 함수 호출이 마지막에 일어나고 추가적인 작업이 없을 때,

새로운 스택 프레임을 생성하지 않고 현재 스택 프레임을 재사용함으로써 메모리 사용을 줄이는 최적화 기법이다.

재귀 호출이 깊어질 때 스택 오버플로우를 방지하고 성능을 향상시킬 수 있다.

꼬리 호출 최적화가 없으면, 각 재귀 호출마다 새로운 스택 프레임이 생성되어 스택 메모리를 차지하게 된다.