Java 재귀함수 완전정복: 종료조건부터 꼬리재귀까지 실무 개발자가 알려주는 모든 것

재귀함수란 무엇인가?

재귀함수는 간단히 말해서 자기 자신을 호출하는 함수입니다. 복잡한 문제를 작은 단위로 나누어 해결하는 분할 정복(Divide and Conquer) 방식의 핵심이죠.

public class RecursionExample {
    public static void greet(int count) {
        if (count <= 0) {  // 종료 조건
            return;
        }
        
        System.out.println("안녕하세요! " + count);
        greet(count - 1);  // 재귀 호출
    }
    
    public static void main(String[] args) {
        greet(3);
    }
}

 

위 코드를 실행하면 다음과 같은 결과가 나타납니다.

안녕하세요! 3
안녕하세요! 2
안녕하세요! 1

재귀함수의 핵심 구성요소

모든 재귀함수는 반드시 두 가지 요소를 가져야 합니다.

 

1. 기저 조건 (Base Case)

재귀 호출을 멈추는 조건입니다. 이것이 없으면 무한히 자신을 호출하다가 스택 오버플로우가 발생합니다.

 

2. 재귀 호출 (Recursive Call)

문제를 더 작은 단위로 나누어 자신을 다시 호출하는 부분입니다.

public class FactorialExample {
    public static int factorial(int n) {
        // 기저 조건
        if (n <= 1) {
            return 1;
        }
        
        // 재귀 호출
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5)); // 결과: 120
    }
}

재귀함수 작동 원리 깊이 이해하기

팩토리얼 5!의 계산 과정을 단계별로 살펴보겠습니다.

factorial(5) 호출
│
├─ n = 5, n > 1이므로 5 * factorial(4) 계산 필요
   └─ factorial(4) 호출
      │
      ├─ n = 4, n > 1이므로 4 * factorial(3) 계산 필요
         └─ factorial(3) 호출
            │
            ├─ n = 3, n > 1이므로 3 * factorial(2) 계산 필요
               └─ factorial(2) 호출
                  │
                  ├─ n = 2, n > 1이므로 2 * factorial(1) 계산 필요
                     └─ factorial(1) 호출
                        │
                        └─ n = 1, 기저조건 만족 → return 1

 

이제 스택에서 값들이 계산되면서 반환됩니다.

factorial(1) → 1
factorial(2) → 2 * 1 = 2
factorial(3) → 3 * 2 = 6
factorial(4) → 4 * 6 = 24
factorial(5) → 5 * 24 = 120

재귀의 메모리 문제와 스택 오버플로우

재귀함수의 가장 큰 문제점은 메모리 사용량입니다. 함수가 호출될 때마다 새로운 스택 프레임이 생성되어 메모리를 차지합니다.

public class StackOverflowDemo {
    public static int badRecursion(int n) {
        System.out.println("현재 n: " + n);
        return badRecursion(n + 1);  // 종료 조건이 없음!
    }
    
    public static void main(String[] args) {
        // 주의: 이 코드는 StackOverflowError를 발생시킵니다!
        // badRecursion(1);
    }
}

 

실제로 큰 숫자로 팩토리얼을 계산해보면

public class LargeFactorial {
    public static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        // 이 코드는 스택 오버플로우를 발생시킬 수 있습니다
        System.out.println(factorial(10000));
    }
}

꼬리재귀(Tail Recursion)란?

꼬리재귀는 재귀함수의 메모리 문제를 해결하는 패턴입니다. 핵심은 재귀 호출이 함수의 마지막 동작이 되도록 하는 것입니다.

 

일반 재귀 vs 꼬리재귀 비교

일반 재귀

public static int normalRecursion(int n) {
    if (n <= 1) return 1;
    return n * normalRecursion(n - 1);  // 호출 후 곱셈 연산이 남아있음
}

 

꼬리재귀

public static int tailRecursion(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return tailRecursion(n - 1, n * accumulator);  // 호출이 마지막 동작
}

// 사용법
public static int factorial(int n) {
    return tailRecursion(n, 1);
}

 

꼬리재귀의 핵심은 중간 결과를 누적변수(accumulator)에 저장하여 재귀 호출 시 함께 전달하는 것입니다.

꼬리재귀 동작 과정 분석

tailRecursion(5, 1)의 실행 과정

tailRecursion(5, 1)
│
├─ n = 5 > 1, tailRecursion(4, 5*1) = tailRecursion(4, 5) 호출
   │
   ├─ n = 4 > 1, tailRecursion(3, 4*5) = tailRecursion(3, 20) 호출
      │
      ├─ n = 3 > 1, tailRecursion(2, 3*20) = tailRecursion(2, 60) 호출
         │
         ├─ n = 2 > 1, tailRecursion(1, 2*60) = tailRecursion(1, 120) 호출
            │
            └─ n = 1, 기저조건 만족 → return 120

 

일반 재귀와 달리 꼬리재귀는 각 호출에서 완성된 결과를 바로 전달하므로, 이론적으로는 스택을 재사용할 수 있습니다.

Java의 꼬리재귀 최적화 한계

아쉽게도 Java는 꼬리재귀 최적화(Tail Call Optimization)를 지원하지 않습니다. 따라서 꼬리재귀로 작성해도 여전히 스택 메모리를 사용합니다.

public class TailRecursionTest {
    public static long tailSum(int n, long acc) {
        if (n <= 0) return acc;
        return tailSum(n - 1, acc + n);
    }
    
    public static void main(String[] args) {
        // 여전히 큰 숫자에서는 StackOverflowError 발생
        System.out.println(tailSum(100000, 0));
    }
}

실무에서 활용하는 재귀함수 예제들

1. 피보나치 수열

public class Fibonacci {
    // 일반 재귀 (비효율적)
    public static int fibonacciNormal(int n) {
        if (n <= 1) return n;
        return fibonacciNormal(n - 1) + fibonacciNormal(n - 2);
    }
    
    // 꼬리재귀 스타일
    public static int fibonacciTail(int n, int a, int b) {
        if (n == 0) return a;
        if (n == 1) return b;
        return fibonacciTail(n - 1, b, a + b);
    }
    
    public static int fibonacci(int n) {
        return fibonacciTail(n, 0, 1);
    }
}

 

2. 이진 탐색

public class BinarySearch {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        // 기저 조건
        if (left > right) return -1;
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) 
            return binarySearch(arr, target, left, mid - 1);
        else 
            return binarySearch(arr, target, mid + 1, right);
    }
    
    public static int search(int[] arr, int target) {
        return binarySearch(arr, target, 0, arr.length - 1);
    }
}

 

3. 트리 순회

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class TreeTraversal {
    // 전위 순회
    public static void preorderTraversal(TreeNode node) {
        if (node == null) return;  // 기저 조건
        
        System.out.print(node.val + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
    
    // 중위 순회
    public static void inorderTraversal(TreeNode node) {
        if (node == null) return;
        
        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }
}

재귀 vs 반복문: 언제 무엇을 사용할까?

재귀함수를 사용하는 경우

• 트리나 그래프 구조를 다룰 때
• 분할 정복 알고리즘 구현 시
• 문제의 구조가 재귀적일 때
• 코드의 가독성이 중요할 때

반복문을 사용하는 경우

• 성능이 중요한 상황
• 스택 오버플로우가 우려될 때
• 단순한 반복 작업
• 메모리 사용량을 최소화해야 할 때

성능 비교 및 최적화 팁

public class PerformanceComparison {
    // 재귀 버전
    public static long factorialRecursive(int n) {
        if (n <= 1) return 1;
        return n * factorialRecursive(n - 1);
    }
    
    // 반복문 버전
    public static long factorialIterative(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
    public static void main(String[] args) {
        int n = 20;
        
        long start = System.nanoTime();
        long recursiveResult = factorialRecursive(n);
        long recursiveTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        long iterativeResult = factorialIterative(n);
        long iterativeTime = System.nanoTime() - start;
        
        System.out.println("재귀 결과: " + recursiveResult + ", 시간: " + recursiveTime + "ns");
        System.out.println("반복 결과: " + iterativeResult + ", 시간: " + iterativeTime + "ns");
    }
}

메모이제이션으로 재귀 성능 향상시키기

같은 값을 반복 계산하는 재귀함수는 메모이제이션으로 최적화할 수 있습니다.

import java.util.HashMap;
import java.util.Map;

public class MemoizedFibonacci {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fibonacci(int n) {
        if (n <= 1) return n;
        
        // 이미 계산된 값이면 바로 반환
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // 새로 계산하고 저장
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("피보나치 40번째: " + fibonacci(40));
    }
}

실무 개발에서의 재귀함수 활용 팁

1. 항상 종료 조건을 먼저 작성하세요

public static int someRecursiveFunction(int n) {
    // 1단계: 종료 조건부터 작성
    if (/* 종료 조건 */) {
        return /* 기본값 */;
    }
    
    // 2단계: 재귀 로직 작성
    return /* 재귀 호출과 처리 */;
}

 

2. 입력값의 범위를 고려하세요

public static long factorial(int n) {
    // 입력값 검증
    if (n < 0) {
        throw new IllegalArgumentException("음수는 팩토리얼을 계산할 수 없습니다.");
    }
    if (n > 20) {  // long 타입 범위 고려
        throw new IllegalArgumentException("너무 큰 수입니다.");
    }
    
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

 

3. 디버깅 시에는 호출 스택을 활용하세요

public static int debug_factorial(int n, int depth) {
    String indent = "  ".repeat(depth);
    System.out.println(indent + "factorial(" + n + ") 호출");
    
    if (n <= 1) {
        System.out.println(indent + "기저조건: return 1");
        return 1;
    }
    
    int result = n * debug_factorial(n - 1, depth + 1);
    System.out.println(indent + "return " + n + " * " + (result/n) + " = " + result);
    return result;
}

 

재귀함수는 복잡해 보이지만, 핵심 원리를 이해하고 나면 정말 강력한 도구입니다. 특히 트리 구조나 분할 정복 문제에서는 재귀 없이는 해결하기 어려운 경우가 많아요.

 

하지만 Java에서는 꼬리재귀 최적화를 지원하지 않으므로, 성능이 중요한 상황에서는 반복문이나 메모이제이션 같은 최적화 기법을 함께 고려해야 합니다.

 

실무에서는 코드의 가독성과 성능 사이의 균형을 잘 맞추는 것이 중요합니다. 작은 입력값에 대해서는 재귀를 통해 코드를 명확하게 작성하고, 큰 입력값이 예상되는 경우에는 반복문이나 동적 프로그래밍을 고려해보세요.

 

여러분도 이제 재귀함수를 두려워하지 마시고, 적절한 상황에서 활용해보세요. 처음엔 어렵겠지만, 연습을 통해 점점 친숙해질 거예요!