[Java] 재귀 함수

재귀(Recursion)

    - 원래의 자리로 되돌아가거나 되돌아옴

    - 문제를 동일한 구조의 더 작은 문제로 나누고, 작은 문제를 해결함으로써 전체 문제를 해결하는 방법

    - 알고리즘 문제의 많은 부분을 차지하며, 재귀를 사용하면 코드가 간결하고 이해하기 쉬워짐

 

재귀 함수

    - 자기 자신을 호출하는 함수

    - 문제를 점점 작은 단위로 쪼갤 수 있어야 하고, 재귀 호출이 종료되는 시점이 존재해야 사용 가능

---

재귀 함수를 사용하기 적합할 때

    - 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

    - 변수 사용을 줄여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

 

재귀함수의 장점

    - 불필요한 반복문을 사용하지 않아 코드가 간결해지고 수정이 쉬워짐

    - 반복문에 비해 많은 수의 변수를 사용할 필요 없음

 

재귀함수의 단점

    - 반복문에 비해 코드의 흐름을 직관적으로 파악하기 어려움

    - 반복문에 비해 메모리를 더 많이 사용함

    - 메서드 호출/종료 후 복귀를 위한 컨텍스트 스위칭 비용 발생

        컨텍스트 스위칭 : 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것

---

재귀적으로 사고하기

    1. 재귀 함수의 입력값과 출력값 정의하기

        - 문제를 가장 추상적으로, 또는 가장 단순하게 정의

    2. 문제를 쪼개고 경우의 수를 나누기

        - 입력값이나 문제의 순서, 크기를 기준으로 쪼개고, 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눔

    3. 단순한 문제 해결하기

        - 가장 해결하기 쉬운 문제인 재귀의 기초(base case)부터 해결

        - 재귀의 기초는 함수 구현 시 재귀의 탈출 조건을 구성

    4. 복잡한 문제 해결하기

        - 남아있는 경우의 수(recursive case) 해결

---

반복문 vs 재귀함수 예제: 1부터 정수 n까지의 합계 출력

public class IterationExample {	// 반복문 예제
    public int sumInt(int n) {
        int result = 0;

        // 반복문(for문 사용)
        for (int i = 0; i <= n; i++) result += i;

        return result;
    }
}

public class RecursionExample {	// 재귀함수 예제
    public int sumInt(int n) {
        // 1. 입력값과 출력값 정의 : 입력값, 출력값 모두 int
        // 2. 경우의 수 나누기 : base case, recursive case

        // 3. Base case(문제를 더 이상 쪼갤 수 없는 경우) 해결
        if (n == 0) {   // 재귀의 기초(base case), 재귀 탈출 조건
            return 0;
        }

        // 4. Recursive Case(남아있는 경우의 수) 해결
        return n + sumInt(n - 1);   // 재귀를 통해 더 작은 단위로 쪼개서 해결
    }
}

---