자료구조와 알고리즘

재귀

begin-play 2026. 8. 26. 11:22

재귀(Recursion) — TIL 정리

1. 재귀란?

재귀(Recursion)란 함수가 자기 자신을 다시 호출하는 것이다.

가장 기본적인 형태는 다음과 같다.

void Function()
{
    Function();
}

Function()이 실행되면 다시 Function()을 호출하고, 그 함수가 다시 Function()을 호출한다.

Function()
 └─ Function()
     └─ Function()
         └─ Function()
             └─ ...

이렇게 계속 호출되면 프로그램이 끝나지 않고 호출 스택이 계속 쌓이게 된다.

결국 Stack Overflow가 발생한다.

따라서 정상적인 재귀 함수에는 반드시 종료 조건이 필요하다.

2. 재귀 함수의 두 가지 핵심

재귀 함수를 이해할 때 가장 중요한 것은 Base Case와 Recursive Case이다.

2-1. Base Case

재귀를 멈추는 조건이다.

if (n == 0)
{
    return;
}

n == 0이 되면 더 이상 자기 자신을 호출하지 않는다.

즉,

Base Case
→ 재귀를 언제 멈출 것인가?

를 결정한다.

2-2. Recursive Case

자기 자신을 다시 호출하는 부분이다.

Function(n - 1);

즉 재귀 함수는 기본적으로 다음과 같은 구조를 가진다.

void Function(int n)
{
    if (n == 0)
    {
        return;
    }

    Function(n - 1);
}

정리하면:

재귀 함수
├── Base Case
│   └── 재귀 종료
│
└── Recursive Case
    └── 자기 자신을 다시 호출

재귀 문제를 풀 때는 항상 먼저 Base Case가 무엇인지 찾고, 그다음 문제를 어떻게 더 작은 문제로 만들 것인지 생각해야 한다.

3. 호출 스택(Call Stack)

재귀에서 가장 중요한 개념이다.

함수를 호출하면 프로그램은 해당 함수의 실행 정보 등을 호출 스택(Call Stack)에 저장한다.

예를 들어 다음과 같은 코드가 있다고 하자.

void A()
{
    B();
}

void B()
{
    C();
}

void C()
{
}

A()를 호출하면:

A()

A()가 B()를 호출하면:

B()
A()

B()가 C()를 호출하면:

C()
B()
A()

이 상태에서 C()가 끝나면:

B()
A()

B()가 끝나면:

A()

A()가 끝나면:

비어 있음

즉 가장 마지막에 들어간 함수가 가장 먼저 빠진다.

이것이 바로 LIFO(Last In, First Out)이다.

앞에서 배운 스택 자료구조가 실제 함수 호출에도 사용되는 것이라고 생각할 수 있다.

4. 재귀에서 호출 스택이 어떻게 움직이는가

다음 코드를 보자.

void CountDown(int n)
{
    if (n == 0)
    {
        return;
    }

    cout << n << endl;
    CountDown(n - 1);
}

다음과 같이 호출한다.

CountDown(3);

① CountDown(3)

CountDown(3)

n == 0이 아니므로 3을 출력하고 CountDown(2)를 호출한다.

CountDown(3)
CountDown(2)

② CountDown(2)

다시 CountDown(1)을 호출한다.

CountDown(3)
CountDown(2)
CountDown(1)

③ CountDown(1)

다시 CountDown(0)을 호출한다.

CountDown(3)
CountDown(2)
CountDown(1)
CountDown(0)

④ CountDown(0)

Base Case에 도달한다.

if (n == 0)
{
    return;
}

따라서 더 이상 자기 자신을 호출하지 않는다.

이제 재귀가 풀리기 시작한다.

CountDown(0) 종료
↓
CountDown(1) 종료
↓
CountDown(2) 종료
↓
CountDown(3) 종료

이처럼 Base Case를 만난 후 쌓여 있던 함수 호출이 역순으로 빠져나오는 과정을 흔히 Unwinding이라고 한다.

5. 재귀에서 가장 헷갈리는 부분

다음 코드를 보자.

void Test(int n)
{
    if (n == 0)
    {
        return;
    }

    cout << "들어감 : " << n << endl;

    Test(n - 1);

    cout << "나옴 : " << n << endl;
}

다음과 같이 호출한다.

Test(3);

출력 결과는:

들어감 : 3
들어감 : 2
들어감 : 1
나옴 : 1
나옴 : 2
나옴 : 3

이다.

왜냐하면 Test(3)이 바로 "나옴 : 3"을 출력하는 것이 아니기 때문이다.

먼저:

Test(2);

를 끝내야 한다.

그다음 Test(2)도:

Test(1);

을 끝내야 한다.

따라서 호출 스택은:

Test(3)
Test(2)
Test(1)
Test(0)

까지 쌓인다.

그리고 Test(0)이 종료된 후:

Test(0) 제거
Test(1) 제거 → "나옴 : 1"
Test(2) 제거 → "나옴 : 2"
Test(3) 제거 → "나옴 : 3"

순서로 실행된다.

따라서 재귀에서는 재귀 호출 아래에 어떤 코드가 있느냐도 매우 중요하다.

Test(n - 1);

cout << "나옴";

이 경우 Test(n - 1)이 모두 끝난 후 "나옴"이 실행된다.

즉 재귀는 내려갈 때와 올라올 때 실행 순서가 다를 수 있다.

6. Factorial(팩토리얼)

재귀를 이해하는 대표적인 예제이다.

팩토리얼은 다음과 같다.

5! = 5 × 4 × 3 × 2 × 1

그리고:

0! = 1

이다.

팩토리얼에는 다음과 같은 관계가 있다.

n! = n × (n - 1)!

이 관계를 코드로 그대로 옮길 수 있다.

int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }

    return n * Factorial(n - 1);
}

Factorial(5)를 호출하면:

Factorial(5)
= 5 × Factorial(4)
= 5 × 4 × Factorial(3)
= 5 × 4 × 3 × Factorial(2)
= 5 × 4 × 3 × 2 × Factorial(1)
= 5 × 4 × 3 × 2 × 1 × Factorial(0)

Factorial(0)에서 Base Case를 만나:

return 1;

을 반환한다.

이제 역순으로 계산된다.

Factorial(0) → 1
Factorial(1) → 1
Factorial(2) → 2
Factorial(3) → 6
Factorial(4) → 24
Factorial(5) → 120

즉 Factorial은 재귀 호출이 먼저 스택에 쌓이고, Base Case에 도달한 뒤 결과가 역순으로 반환되는 과정을 이해하기 좋은 예제이다.

7. Fibonacci(피보나치)

피보나치 수열은:

0, 1, 1, 2, 3, 5, 8, 13, 21...

이다.

피보나치의 규칙은:

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

이다.

이를 재귀로 작성하면:

int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

예를 들어:

Fibonacci(5);

를 호출하면 다음과 같이 분리된다.

                F(5)
              /     \
           F(4)     F(3)
          /   \     /   \
       F(3) F(2) F(2) F(1)

여기서 중요한 문제가 발생한다.

F(3)이나 F(2)처럼 같은 값에 대한 계산이 여러 번 반복된다.

따라서 단순 재귀 방식의 Fibonacci는 매우 비효율적이다.

시간 복잡도는 대략 O(2ⁿ) 수준으로 증가한다.

이것을 통해 알 수 있는 것은:

재귀라고 해서 항상 효율적인 것은 아니다.

재귀 호출이 한 번 발생하는지, 여러 갈래로 발생하는지를 확인해야 한다.

8. 재귀의 시간 복잡도

재귀 함수도 시간 복잡도를 계산해야 한다.

다음과 같은 함수가 있다고 하자.

void Function(int n)
{
    if (n == 0)
        return;

    Function(n - 1);
}

호출 흐름은:

n
↓
n - 1
↓
n - 2
↓
...
↓
0

이다.

한 번씩 호출되므로 전체 호출 횟수는 n에 비례한다.

따라서 시간 복잡도는:

O(n)

이다.

하지만 Fibonacci처럼:

Fibonacci(n - 1);
Fibonacci(n - 2);

두 개의 재귀 호출이 계속 발생하면 호출 수가 급격하게 증가한다.

        F(n)
       /    \
    F(n-1)  F(n-2)
    /  \     /  \
   ... ...  ... ...

따라서 재귀에서는 단순히:

재귀 → O(n)

이라고 생각하면 안 된다.

재귀 호출이 어떤 형태로 발생하는지를 확인해야 한다.

9. 재귀의 공간 복잡도

재귀에서는 시간 복잡도뿐만 아니라 호출 스택이 얼마나 깊게 쌓이는지도 중요하다.

예를 들어:

Function(n);

을 호출했을 때 재귀 깊이가 n이라면 호출 스택에도 최대 n개의 함수 호출이 쌓일 수 있다.

따라서:

Function(int n)
{
    Function(n - 1);
}

같은 함수의 공간 복잡도는:

O(n)

이 된다.

즉 재귀에서는 다음 두 가지를 모두 고려해야 한다.

시간 복잡도
+
호출 스택에 필요한 공간

10. 재귀 → 반복문 변환

많은 재귀 함수는 반복문으로 바꿀 수 있다.

예를 들어 Factorial:

int Factorial(int n)
{
    if (n == 0)
        return 1;

    return n * Factorial(n - 1);
}

을 반복문으로 바꾸면:

int Factorial(int n)
{
    int result = 1;

    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

두 코드의 결과는 같다.

재귀
5 → 4 → 3 → 2 → 1 → 0

반복문
1 → 2 → 3 → 4 → 5

반복문은 일반적으로 함수 호출에 따른 호출 스택을 사용하지 않기 때문에 공간 측면에서 유리할 수 있다.

11. 그런데 왜 재귀를 사용하는가?

그렇다면 모든 재귀를 반복문으로 바꾸면 되는 것처럼 보인다.

하지만 재귀가 훨씬 자연스러운 문제들이 있다.

대표적으로:

트리 순회
DFS
Divide and Conquer
백트래킹
폴더 구조 탐색
그래프 탐색

등이 있다.

특히 트리는 재귀와 매우 잘 맞는다.

예를 들어:

B 밑에 자식이 있고, 그 자식 밑에도 또 자식이 있을 수 있다.

따라서:

노드를 처리한다
→ 자식 노드를 처리한다
→ 그 자식의 자식 노드를 처리한다
→ ...

와 같은 구조를 재귀로 표현하기 좋다.

12. Tree Traversal

트리 순회는 트리의 모든 노드를 특정한 순서로 방문하는 것이다.

예를 들어:

라는 트리가 있다고 하자.

Preorder

순서는:

Root
Left
Right

이다.

따라서:

A B D E C

순서로 방문한다.

재귀 코드는 다음과 같은 형태이다.

void Preorder(Node* node)
{
    if (node == nullptr)
        return;

    cout << node->value;
    Preorder(node->left);
    Preorder(node->right);
}

여기서:

Preorder(node->left);
Preorder(node->right);

가 재귀 호출이다.

Inorder

순서는:

Left
Root
Right

이다.

결과:

D B E A C

Postorder

순서는:

Left
Right
Root

이다.

결과:

D E B C A

즉 재귀 호출을 어떤 위치에 배치하느냐에 따라 트리 순회 순서가 달라진다.

13. DFS와 재귀

DFS는 Depth First Search, 즉 깊이 우선 탐색이다.

예를 들어:

A
├── B
│   ├── D
│   └── E
└── C

DFS는 한 방향으로 최대한 깊게 들어가는 방식이다.

재귀로 작성하면 개념적으로:

void DFS(Node* node)
{
    if (node == nullptr)
        return;

    방문(node);

    DFS(node->left);
    DFS(node->right);
}

와 같은 형태가 된다.

여기서 중요한 점은:

DFS 자체가 재귀라는 의미는 아니다.

DFS는 재귀 방식으로 구현할 수도 있고, 반복문 + Stack으로 구현할 수도 있다.

재귀 DFS
→ 시스템의 Call Stack 사용

반복문 DFS
→ 직접 만든 Stack 사용

결국 둘은 비슷한 원리를 사용한다.

14. Divide and Conquer

Divide and Conquer(분할 정복)는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 다음 각각 해결하고 결과를 합치는 방법이다.

대표적인 알고리즘은:

Merge Sort
Quick Sort
Binary Search

등이 있다.

예를 들어 Binary Search는:

[1 2 3 4 5 6 7 8 9]

에서 가운데 값을 확인한다.

찾는 값이 가운데 값보다 작으면:

왼쪽만 탐색

찾는 값이 가운데 값보다 크면:

오른쪽만 탐색

한다.

따라서 문제의 크기가:

9개
↓
4개
↓
2개
↓
1개

처럼 계속 줄어든다.

그래서 Binary Search의 시간 복잡도는:

O(log n)

이다.

15. 재귀 문제를 푸는 사고방식

재귀 문제를 처음 봤을 때 바로 코드를 작성하기보다는 다음 순서로 생각하는 것이 좋다.

① 가장 작은 문제는 무엇인가?

먼저 Base Case를 찾는다.

예:

if (n == 0)
    return 1;

② 현재 문제를 더 작은 문제로 어떻게 만들 것인가?

예를 들어 Factorial은:

Factorial(n)
→ n × Factorial(n - 1)

으로 만들 수 있다.

③ 작은 문제는 해결된다고 가정한다

이 부분이 재귀 사고방식에서 중요하다.

예를 들어:

Factorial(n - 1)

이 정상적으로 결과를 반환한다고 가정한다.

그러면:

return n * Factorial(n - 1);

이라고 작성할 수 있다.

내부의 Factorial(n - 1)이 어떻게 계산되는지 하나하나 직접 작성할 필요가 없다.

함수 자기 자신이 더 작은 문제를 해결하도록 맡기는 것이다.

④ 호출 스택을 따라가 본다

예를 들어:

Factorial(5)
Factorial(4)
Factorial(3)
Factorial(2)
Factorial(1)
Factorial(0)

까지 내려간다.

그리고 Base Case를 만난다.

그 후 다시:

0 → 1 → 2 → 6 → 24 → 120

순서로 올라온다.

따라서 재귀 문제를 풀 때는 내려가는 과정과 올라오는 과정을 둘 다 생각해야 한다.

16. 재귀에서 자주 하는 실수

Base Case가 없는 경우

void Function(int n)
{
    Function(n - 1);
}

재귀를 멈출 조건이 없기 때문에 계속 호출된다.

결국 Stack Overflow가 발생한다.

Base Case에 도달하지 못하는 경우

void Function(int n)
{
    if (n == 0)
        return;

    Function(n + 1);
}

현재 n이 증가하기 때문에 0에 도달하지 못한다.

따라서 재귀가 끝나지 않는다.

문제의 크기가 줄어들지 않는 경우

Function(n);

을 그대로 다시 호출하면 문제의 크기가 변하지 않는다.

일반적으로 재귀에서는:

현재 문제
↓
더 작은 문제
↓
더 작은 문제
↓
Base Case

라는 흐름이 만들어져야 한다.

17. 재귀의 장점과 단점

장점

복잡한 구조를 간결하게 표현할 수 있다.
트리 구조와 잘 맞는다.
DFS 구현이 간단하다.
Divide and Conquer 알고리즘을 표현하기 좋다.
문제의 수학적 정의를 코드로 옮기기 쉽다.

단점

호출 스택을 사용한다.
재귀 깊이가 너무 깊으면 Stack Overflow가 발생할 수 있다.
같은 계산을 반복하면 매우 느려질 수 있다.
반복문보다 실행 구조를 이해하기 어려울 수 있다.
호출 스택 때문에 추가적인 메모리를 사용할 수 있다.

18. 재귀에서 반드시 기억해야 할 핵심

재귀는 단순히 "함수가 자기 자신을 호출한다"라고만 이해하면 부족하다.

진짜 핵심은 다음과 같다.

재귀
│
├─ Base Case
│    └─ 재귀 종료
│
└─ Recursive Case
     └─ 자기 자신 호출

그리고 실제 실행 과정은:

즉:

함수가 호출될 때 호출 스택에 쌓이고, Base Case에 도달하면 하나씩 빠져나오면서 이전 함수가 이어서 실행된다.

이것이 재귀의 가장 중요한 원리이다.

19. 5단계 핵심 키워드 정리

개념의미

Recursion	함수가 자기 자신을 호출하는 것
Base Case	재귀를 종료하는 조건
Recursive Case	자기 자신을 다시 호출하는 부분
Call Stack	함수 호출 정보를 저장하는 스택
Stack Overflow	호출 스택이 지나치게 커진 상태
Unwinding	Base Case 이후 재귀 호출이 역순으로 종료되는 과정
Factorial	재귀를 이해하는 대표적인 예
Fibonacci	재귀 호출이 여러 갈래로 발생하는 대표적인 예
Tree Traversal	트리 구조를 탐색하는 방법
DFS	깊이 우선 탐색
Divide and Conquer	문제를 작은 문제로 나누어 해결하는 방법
Time Complexity	재귀 호출 횟수를 고려한 시간 복잡도
Space Complexity	호출 스택의 최대 깊이를 고려한 공간 복잡도

20. 지금까지 배운 자료구조와 재귀의 연결

스택과 직접 연결된다.

Stack
↓
LIFO
↓
가장 나중에 들어온 것이 가장 먼저 나옴
↓
Recursion
↓
함수 호출이 Call Stack에 쌓임
↓
Base Case 도달
↓
가장 마지막에 호출된 함수부터 종료

즉 스택 자료구조를 배운 이유 중 하나가 재귀를 이해하는 데에도 연결된다.

앞으로 배우게 될 자료구조와 알고리즘에서도 계속 연결된다.

Stack
  ↓
Recursion
  ↓
Tree
  ↓
DFS
  ↓
Graph

21. 5단계에서 꼭 기억할 것

① 재귀에는 Base Case가 필요하다.

재귀를 언제 끝낼 것인지 정해야 한다.

② Recursive Case에서는 문제의 크기가 점점 작아져야 한다.

현재 문제를 더 작은 문제로 만들어야 Base Case에 도달할 수 있다.

③ 재귀 호출은 Call Stack에 쌓인다.

함수가 호출될 때마다 해당 함수의 실행 정보가 스택에 쌓인다.

④ Base Case에 도달하면 쌓였던 함수들이 역순으로 빠져나온다.

LIFO 구조이기 때문에 가장 마지막에 호출된 함수가 먼저 종료된다.

⑤ 재귀의 시간 복잡도와 공간 복잡도는 따로 생각해야 한다.

호출 횟수가 얼마나 되는지뿐만 아니라 호출 스택이 얼마나 깊게 쌓이는지도 확인해야 한다.

⑥ 재귀는 반복문으로 바꿀 수 있는 경우가 많다.

하지만 트리, DFS, Divide and Conquer처럼 재귀로 표현하는 것이 자연스러운 문제도 많다.

한 문장으로 정리

재귀는 자기 자신을 호출하면서 문제를 더 작은 문제로 나누고, Base Case에 도달한 뒤 Call Stack에 쌓였던 함수들이 역순으로 실행되면서 문제를 해결하는 방법이다.

'자료구조와 알고리즘' 카테고리의 다른 글

정렬 알고리즘 (0)	2026.08.28
탐색 알고리즘 (0)	2026.08.27
스택과 큐 (0)	2026.08.25
연결 리스트 (0)	2026.08.24
배열과 문자열 (0)	2026.08.21

현재글재귀

begin-play 님의 블로그

begin-play 님의 블로그 입니다.

Today :
Yesterday :

« 2026/09 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

재귀

재귀(Recursion) — TIL 정리

1. 재귀란?

2. 재귀 함수의 두 가지 핵심

2-1. Base Case

2-2. Recursive Case

3. 호출 스택(Call Stack)

4. 재귀에서 호출 스택이 어떻게 움직이는가

① CountDown(3)

② CountDown(2)

③ CountDown(1)

④ CountDown(0)

5. 재귀에서 가장 헷갈리는 부분

6. Factorial(팩토리얼)

7. Fibonacci(피보나치)

8. 재귀의 시간 복잡도

9. 재귀의 공간 복잡도

10. 재귀 → 반복문 변환

11. 그런데 왜 재귀를 사용하는가?

12. Tree Traversal

Preorder

Inorder

Postorder

13. DFS와 재귀

14. Divide and Conquer

15. 재귀 문제를 푸는 사고방식

① 가장 작은 문제는 무엇인가?

② 현재 문제를 더 작은 문제로 어떻게 만들 것인가?

③ 작은 문제는 해결된다고 가정한다

④ 호출 스택을 따라가 본다

16. 재귀에서 자주 하는 실수

Base Case가 없는 경우

Base Case에 도달하지 못하는 경우

문제의 크기가 줄어들지 않는 경우

17. 재귀의 장점과 단점

장점

단점

18. 재귀에서 반드시 기억해야 할 핵심

19. 5단계 핵심 키워드 정리

20. 지금까지 배운 자료구조와 재귀의 연결

21. 5단계에서 꼭 기억할 것

① 재귀에는 Base Case가 필요하다.

② Recursive Case에서는 문제의 크기가 점점 작아져야 한다.

③ 재귀 호출은 Call Stack에 쌓인다.

④ Base Case에 도달하면 쌓였던 함수들이 역순으로 빠져나온다.

⑤ 재귀의 시간 복잡도와 공간 복잡도는 따로 생각해야 한다.

⑥ 재귀는 반복문으로 바꿀 수 있는 경우가 많다.

한 문장으로 정리

'자료구조와 알고리즘' 카테고리의 다른 글

'자료구조와 알고리즘'의 다른글

관련글

티스토리툴바