자료구조 · 알고리즘 기초집LESSON 15

재귀 함수: 종료 조건과 호출 흐름 이해하기

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

15강. 재귀 함수: 종료 조건과 호출 흐름 이해하기

1. 이번 강의에서 해결할 문제

트리나 분할 정복처럼 같은 구조가 반복되는 문제는 반복문만으로 표현하면 상태 관리가 복잡할 수 있지만, 종료 조건이 없는 재귀는 스택을 소진합니다.

2. 학습 목표

3. 핵심 개념

재귀 함수는 더 작은 같은 문제를 호출하고, 더 나눌 수 없는 기본 사례에서 값을 직접 반환합니다. 각 호출의 지역 변수와 돌아갈 위치는 호출 스택에 쌓입니다. 따라서 호출 깊이가 너무 크면 StackOverflowError가 날 수 있습니다. Java는 꼬리 재귀 최적화를 언어 계약으로 보장하지 않으므로 단순 선형 반복은 반복문이 더 안전할 수 있습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/RecursiveStageScore.java

src/RecursiveStageScore.java
public class RecursiveStageScore {
    static int total(int[] stageScores, int index) {
        if (index == stageScores.length) return 0;
        return stageScores[index] + total(stageScores, index + 1);
    }

    static int totalIterative(int[] stageScores) {
        int sum = 0;
        for (int score : stageScores) sum += score;
        return sum;
    }

    public static void main(String[] args) {
        int[] scores = {100, 250, 400};
        System.out.println(total(scores, 0));
        System.out.println(totalIterative(scores));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/RecursiveStageScore.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/RecursiveStageScore.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\RecursiveStageScore.java
java -cp .\out RecursiveStageScore

예상 결과: 두 방식 모두 총점 750을 출력합니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

index가 배열 길이에 도달하면 0을 반환하고 이전 호출들이 역순으로 값을 더합니다. 각 원소를 한 번 처리해 두 방식 모두 O(n) 시간이지만, 재귀는 O(n) 호출 스택을 사용하고 반복은 O(1) 추가 공간입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ