[Java] 재귀 함수와 스택(Stack)의 개념

 

 

재귀함수를 언제 써야 하는지가 중요한데, 똑같은 동작을 일정한 규칙과 간격을 가진 수들을 처리할 때 사용된다.

재귀함수를 사용할 때 가장 중요한 것은 종료 조건을 설정해서 어디서 멈출지를 정해야 끝없이 반복되는 것을 막을 수 있다는 점이다.

 

또한, 재귀함수의 리턴값이 역순으로 출력되는 것을 보면 스택(Stack) 메모리 구조를 사용함을 알 수 있다.

만약에 역순이 아니라 정순으로 출력되기를 의도한다면, 코드의 순서만 바꿔주면 된다.

---

1. 재귀 함수란?

재귀 함수는 문제를 “더 작은 문제”로 쪼개서 해결하는 방법이다.

 

재귀를 이해하려면 두 가지 핵심 개념을 알아야 한다:

1. 종료 조건 (Base Case)

 • 재귀 함수는 계속 자신을 호출하다 보면 끝없이 반복될 수 있다.

 그래서 어디서 멈출지를 정해야 한다. 종료 조건은 재귀 호출을 멈추고 답을 반환하는 역할을 한다

2. 작은 문제로 쪼개기

• 문제를 점점 더 작은 문제로 나누어서 해결한다.

결국, 작은 문제들이 종료 조건을 만나면서 답이 점점 만들어진다.

 

---

재귀 함수의 예: 숫자 세기

 

문제:

숫자 1부터 n까지 차례로 출력하는 재귀 함수를 만들어보세요.

 

public class RecursionExample {
   public static void printNumbers(int n) {
       if (n == 0) { // 종료조건 : n이 0이면 멈춤
        return;
       }
       printNumbers(n - 1); // n보다 작은 숫자를 출력(작은 문제로 쪼개기)
       System.out.println(n); // 숫자 출력
   }
   
   public static void main(String[] args) {
      printNumbers(5); //1, 2, 3, 4, 5 출력
   }
}

 

재귀의 동작 과정 (단계별)

 

printNumbers(5)를 호출하면 아래와 같이 작동한다:

1. printNumbers(5) → 호출 → printNumbers(4) 호출

2. printNumbers(4) → 호출 → printNumbers(3) 호출

3. printNumbers(3) → 호출 → printNumbers(2) 호출

4. printNumbers(2) → 호출 → printNumbers(1) 호출

5. printNumbers(1) → 호출 → printNumbers(0) 호출

6. 종료 조건에 도달: n == 0 → 아무것도 하지 않고 종료.

7. 이제 역순으로 반환하며 숫자를 출력:

• printNumbers(1) → 1 출력.

• printNumbers(2) → 2 출력.

• printNumbers(3) → 3 출력.

• printNumbers(4) → 4 출력.

• printNumbers(5) → 5 출력.

 

<  System.out.println(n)이 바로 실행되지 않는 이유 >

printNumbers(n - 1);​

이 줄은 재귀 호출을 발생시키며, 현재 함수의 실행을 멈추고 n-1에 대해 먼저 실행되도록 한다.

• 즉, printNumbers(n - 1)이 끝날 때까지 현재 함수는 대기하고 있다.
• 모든 재귀 호출이 종료된 후에야 System.out.println(n)이 실행된다.

 

 

<항상 역순이 되지 않는 경우 - 만약 System.out.println(n)을 먼저 실행하고 싶다면? >

1. 재귀 호출 전에 작업을 수행:
• 호출 전에 작업을 실행하면, 재귀 호출이 진행되는 동안 작업이 정순으로 실행된다.

재귀 호출 전에 출력하도록 순서를 바꾸면 된다.

public static void printNumbers(int n) {
    if (n == 0) { // 종료 조건
        return;
    }
    System.out.println(n); // 숫자 출력 먼저
    printNumbers(n - 1); // n보다 작은 숫자 출력
}​

출력 결과:
5, 4, 3, 2, 1

2. 스택을 사용하지 않는 경우:
• 특정 알고리즘은 재귀 대신 반복문을 사용하거나, 스택 대신 큐(선입선출, FIFO)를 사용해 정순으로 실행할 수 있다.
• 예: BFS(너비 우선 탐색)는 큐를 사용해 정순으로 실행된다.

 

< 재귀가 역순으로 실행되는 이유>

스택의 특성 때문에 일반적으로 재귀는 아래 순서로 진행된다:

1. 호출(스택에 쌓임):
   • 함수가 호출되면, 호출 정보가 스택에 쌓인다.
   • 재귀 호출이 종료 조건에 도달하기 전까지 계속 쌓인다.
2. 반환(스택에서 꺼냄):
  • 종료 조건에 도달하면 반환이 시작된다.
  • 이때 스택의 마지막에 쌓인 호출부터 순차적으로 반환된다.

이 때문에 “재귀 호출이 끝난 뒤”의 작업(예: System.out.println(n))은 역순으로 실행되는 것이다

 

 

스택의 특성(후입선출) 때문에, 재귀 호출 이후의 작업은 일반적으로 역순으로 실행된다.
하지만 작업을 재귀 호출 전에 수행하거나, 다른 자료구조(예: 큐)를 사용하면 정순으로 실행될 수도 있다.

---

2. 재귀의 원리 스택(Stack)

재귀 함수는 컴퓨터의 스택(Stack) 구조를 이용해 작동한다.

 

• 스택이란

  스택은 “접시를 쌓아 올리는” 구조와 비슷하다.

• 후입선출(LIFO, Last In First Out):

 마지막에 들어온 접시가 먼저 나간다. 제일 먼저 들어온 접시는 제일 마지막에 나간다. 

 

 

재귀 호출의 스택 동작:

• 함수가 호출되면 스택에 쌓인다.

• 종료 조건에 도달하면 함수가 하나씩 스택에서 빠지면서 해결된다.

 

그래서 역순으로 반환하여 숫자를 출력하는 것이다. 

---

3. 재귀 함수로 해결하기 좋은 문제

 

재귀는 반복문으로 풀 수 있는 문제를 해결할 수 있다.

하지만, 특히 다음과 같은 문제에 적합하다:

 

1. 팩토리얼 계산 :

n! = n * (n-1)!

 

문제를 점점 작게 나누기 쉬움.

 

2. 피보나치 수열:

F(n) = F(n-1) + F(n-2)

수열 계산 문제.

 

3. 탐색 알고리즘: - 끝지점과 내가 몇 번 반복할지 알지 못하는 경우. 

• 예: 미로 찾기, 그래프 탐색(DFS).

 

4. 분할 정복 문제:

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 (예: 병합 정렬, 퀵 정렬).

 

---

재귀를 연습할 때 주의할 점

1. 항상 종료 조건을 명확히 작성해야 한다.
   • 종료 조건이 없으면 무한 루프에 빠진다.

2. 작은 문제로 쪼개는 논리를 명확히 이해해야 한다.
  • 큰 문제를 작게 쪼개야 재귀가 잘 작동한다.

3. 반복문과 비교하면서 재귀를 연습해야 한다.
   • 재귀와 반복문은 서로 바꿔 쓸 수 있다.