개요

아래의 내용은 java_grammer 레파지토리 C02MethodClass 디렉터리에 저장되어있는 내용을 정리함

• C11RecursiveBasicFlow.java
• C12RecursiveExample.java

---

재귀함수란

• 정의: 함수가 자기 자신을 다시 호출하는 구조.
• 특징
  • 반복문처럼 반복하지만 내부적으로는 스택(Stack) 사용함.
  • 끝낼 조건(base case) 반드시 필요. 없으면 StackOverflowError 남.
• 활용: DFS, 백트래킹, 분할정복, 트리 탐색 등

재귀함수 설계 시 요령

• 반드시 종료라인을 작성해야함
• for문의 바깥쪽과 안쪽의 형식이 수미상관을 이루도록 짜라

---

재귀함수 호출 흐름

기본적으로 재귀는 “들어가고(push), 나오는(pop)” 흐름임.
그걸 눈으로 직접 확인해보는 게 핵심.

package C02MethodClass;

import java.util.ArrayList;
import java.util.List;

public class C11RecursiveBasicFlow {
    public static void main(String[] args) {
        // recur0(0, 3);
        // recur1(0, 3);
        recur2(new ArrayList<>(), 0, 3);
    }

---

recur0() – 매개변수로 값 넘김

public static void recur0(int count, int target) {
    if (count == target) return;

    System.out.println("재귀 호출 전 count : " + count);
    recur0(count + 1, target);
    System.out.println("재귀 호출 후 count : " + count);
}

흐름

단계	호출 방향	복귀 방향
1	count=0 호출 전 출력
2	count=1 호출 전 출력
3	count=2 호출 전 출력
4	count=3 → 종료
		count=2 호출 후 출력
		count=1 호출 후 출력
		count=0 호출 후 출력

즉, “아래로 들어갔다 위로 올라온다” 흐름임.

---

recur1() – 내부 값 변경 후 호출

public static void recur1(int count, int target) {
    if (count == target) return;

    System.out.println("재귀 호출 전 count : " + count);
    count += 1;
    recur1(count, target);
    System.out.println("재귀 호출 후 count : " + count);
}

recur0()이랑 비슷하지만 값 증가를 내부에서 처리함.
복귀 시 찍히는 count 값이 달라짐.

---

recur2() – 객체 매개변수 활용

public static void recur2(List<Integer> myList, int count, int target) {
    if (myList.size() == target) return;

    myList.add(count);
    recur2(myList, count + 1, target);
    System.out.println(myList);
    myList.remove(myList.size() - 1);
}

• List는 참조형이라 호출 사이에서도 같은 객체 공유함.
• 호출 때 add()로 쌓고 복귀 때 remove()로 빼는 구조.
• 백트래킹 구조랑 똑같음.

흐름

호출: [0] → [0,1] → [0,1,2]
복귀: [0,1,2] → [0,1,2] → [0,1,2]

---

재귀 기본 예시들

누적합, 팩토리얼, 피보나치가 가장 기본임.
반복문이랑 재귀 비교하면 확실히 감 잡힘.

package C02MethodClass;

import java.util.Arrays;

public class C12RecursiveExample {
    public static void main(String[] args) {
        int sumAcc = 0;
        for (int i = 1; i <= 10; i++) sumAcc += i;
        System.out.println(sumAcc);

        int recSumAcc = sumAcc(1, 10);
        System.out.println(recSumAcc);

        int factorialByFor = 1;
        for (int i = 1; i <= 5; i++) factorialByFor *= i;
        System.out.println(factorialByFor);

        System.out.println(factorial(5));

        int n1 = 1, n2 = 1, n3 = 0;
        for (int i = 2; i < 11; i++) {
            n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        System.out.println(n3);

        int[] dp = new int[10];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 10; i++) dp[i] = dp[i - 1] + dp[i - 2];
        System.out.println(Arrays.toString(dp));

        System.out.println(fibonacci(10));
    }

---

누적합 (sumAcc)

public static int sumAcc(int start, int end) {
    if (start > end) return 0;
    return start + sumAcc(start + 1, end);
}

흐름

1. f(1,10) → 1 + f(2,10)
2. f(2,10) → 2 + f(3,10)
3. f(10,10) → 10 + f(11,10)
4. f(11,10) → 0 반환

스택 해제

f(10)=10  
f(9)=19  
f(8)=27  
...  
f(1)=55

재귀는 맨 아래까지 갔다가 위로 쌓아올림.

---

팩토리얼 (factorial)

public static int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

흐름

f(5)=5*f(4)
f(4)=4*f(3)
f(3)=3*f(2)
f(2)=2*f(1)
f(1)=1

결과 → 120

---

피보나치 (fibonacci)

public static int fibonacci(int n) {
    if (n <= 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

점화식: f(n)=f(n-1)+f(n-2)
직관적이지만 중복 호출 많음.
복잡도 O(2ⁿ).
→ DP로 풀면 효율적임.

---

재귀 호출 흐름 정리

재귀는 항상 세 단계로 나뉨.

1. 호출 단계 – 문제를 쪼갬
2. 기저 조건 – 멈춤점 도달
3. 복귀 단계 – 쌓인 스택 해제하면서 계산

핵심은 “언제 쌓이고, 언제 풀리는지” 보는 것.
System.out.println() 위치 바꿔가면서 직접 찍어보면 금방 감 옴.

---

정리

• 재귀는 자기 자신 호출 구조임.
• 스택 기반이라 상태가 쌓였다가 위로 풀림.
• 종료 조건(base case) 필수.
• 반복문보다 구조적으로 명확하지만 성능은 주의.
• DFS, 백트래킹, 분할정복 기본 원리.