[자료구조] 재귀(Recursion)

 

🧠 재귀(Recursion)에 대해 알아보자

---

1. 재귀 함수란?

재귀 함수란 자기 자신을 호출하는 함수로, 문제를 작은 단위로 나누어 해결하는 기법입니다.
알고리즘에서 자주 사용되며, 특히 분할 정복이나 백트래킹에 필수적인 도구입니다.

 

즉, 재귀 함수는 자기 자신을 호출하면서, 특정 조건에서 종료(기저 조건, base case)가 이루어지는 함수입니다.

---

2. 재귀 함수의 기본 구조

public void recursiveFunction() {
    // 종료 조건 (Base Case)
    if (조건) {
        return;
    }
    // 자기 자신 호출
    recursiveFunction();
}

 

위의 코드에서 종료 조건(Base Case)은 재귀 호출이 끝날 조건을 명시한 부분입니다.

---

3. 재귀 함수의 작동 원리

재귀 함수는 호출 스택(Call Stack)을 이용하여 작동합니다.
재귀 호출이 발생하면 함수가 스택에 쌓이고, 종료 조건이 만족되면 스택에서 하나씩 제거됩니다.

작동 과정:

1. 함수 호출 → 호출 스택에 저장
2. 종료 조건 도달 시 반환
3. 반환 값을 이용해 다시 계산

 

 

재귀함수 예시

1. 호출 위치에 따른 다른 결과 값

호출 위치가 출력문 위쪽에 위치 할 경우의 예제입니다.

 

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void recursion(int num){
        if (num == 0) return; //종료 조건
        
        String str = "*";

        recursion(num - 1); //재귀 함수 호출
        
        for (int i = 0; i < num; i++) sb.append("*");
        
        System.out.println(sb.toString());
      
        sb.setLength(0);
    }
}

 

 

현재 코드에서는 recursion(num - 1)이 위쪽에 위치해 있습니다. 이는 먼저 재귀 호출을 수행한 뒤, 하위 함수가 모두 실행되고 나서 현재 함수의 작업(별 출력)이 진행됩니다.
System.out.println과 sb.append("*")는 재귀 호출 뒤에 실행되므로, 재귀가 가장 깊은 단계까지 들어간 후 차례로 출력됩니다.

recursion(5)를 호출했을 때의 실행 흐름을 추적해보겠습니다.

호출 순서

• recursion(5) → recursion(4) → recursion(3) → recursion(2) → recursion(1) → recursion(0)(종료 조건)

반환 순서 (호출이 끝난 후 역순으로 실행)

• recursion(0)이 종료되면, 함수가 스택에서 하나씩 반환되면서 아래 코드가 실행됩니다.
• sb.append("*")와 System.out.println이 반환 순서에 따라 실행되므로 출력이 역순으로 보입니다.

 

 

 

호출 위치가 출력문 아래쪽에 위치 할 경우의 예제입니다.

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void recursion(int num){
        if (num == 0) return; //종료 조건
        
        String str = "*";
        
        for (int i = 0; i < num; i++) sb.append("*");
        System.out.println(sb.toString());
        sb.setLength(0);
        
        recursion(num - 1); //재귀 함수 호출
    }
}

 

출력

만약 recursion(num - 1)을 출력 코드 아래로 이동하면, 별을 출력한 후에 재귀를 호출하게 됩니다.

결과는 반대 방향으로 출력될 것입니다:

 

 

📝 적용 문제

https://www.codetree.ai/trails/complete/curated-cards/intro-square-of-each-digit/submissions?page=1&page_size=20

Code Tree | Learning to Code with Confidence

https://www.codetree.ai/trails/complete/curated-cards/intro-fibonacci-using-recursive-function/submissions?page=1&page_size=20

Code Tree | Learning to Code with Confidence