재귀함수와 반복문의 시간복잡도, 그리고 출력 순서가 뒤집히는 이유

프로그래밍에서 같은 작업을 여러 번 수행하는 대표적인 방법에는 반복문과 재귀함수가 있다. 반복문은 for, while과 같은 문법을 사용하고, 재귀함수는 함수가 자기 자신을 다시 호출하는 방식으로 동작한다.

두 방식은 비슷한 결과를 만들 수 있지만, 실행 과정과 메모리 사용 방식에는 중요한 차이가 있다. 특히 재귀 호출문의 앞과 뒤 중 어디에 출력문을 배치하느냐에 따라 출력 순서가 달라진다.

---

1. 반복문이란 무엇인가

반복문은 주어진 조건이 만족되는 동안 특정 코드를 계속 실행하는 문법이다.

다음 코드는 3부터 1까지 출력한다.

#include <stdio.h>

int main(void) {
    for (int i = 3; i >= 1; i--) {
        printf("%d ", i);
    }

    return 0;
}

실행 결과는 다음과 같다.

3 2 1

반복문은 하나의 함수 안에서 변수 i를 변경하면서 같은 코드를 반복해서 실행한다.

 

 

i 가 3부터 1까지 감소하며 출력되는 과정을 나타낸 이미지이다.

---

2. 재귀함수란 무엇인가

재귀함수는 함수 내부에서 자기 자신을 다시 호출하는 함수이다.

다음 코드는 재귀함수를 이용해 3부터 1까지 출력한다.

#include <stdio.h>

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

    printf("%d ", n);
    printNumber(n - 1);
}

int main(void) {
    printNumber(3);
    return 0;
}

함수 내부의 다음 문장이 자기 자신을 다시 호출한다.

printNumber(n - 1);

printNumber(3)을 호출하면 내부적으로 다음과 같이 실행된다.

printNumber(3)
→ printNumber(2)
→ printNumber(1)
→ printNumber(0)

각 함수가 다음 함수에 전달하는 값은 이전 값보다 1 작다. 결국 n이 0이 되면 다음 종료 조건에 의해 재귀 호출이 멈춘다.

if (n == 0) {
    return;
}

재귀함수에는 반드시 종료 조건이 필요하다. 종료 조건이 없다면 함수가 자기 자신을 끝없이 호출한다. 그러면 호출 정보가 메모리에 계속 쌓이고, 결국 스택 오버플로가 발생한다.

재귀함수의 핵심은 다음 두 가지이다.

if (n == 0) return;  // 종료 조건
printNumber(n - 1);  // 재귀 호출

재귀 호출을 엔진이라고 한다면 종료 조건은 브레이크라고 할 수 있다.

 

재귀함수가 자기 자신을 더 작은 값으로 호출하는 모습을 러시아 인형으로 표현한 이미지이다.

 

---

3. 재귀함수는 실제로 어떻게 실행되는가

재귀함수를 정확히 이해하려면 함수 호출이 끝날 때까지 기존 함수가 기다린다는 사실을 알아야 한다.

다음 코드를 살펴본다.

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

    printf("%d ", n);
    printNumber(n - 1);
}

printNumber(3)을 호출하면 먼저 3을 출력한다.

그다음 printNumber(2)를 호출한다. 이때 printNumber(3)이 완전히 종료되는 것은 아니다. 자신이 호출한 printNumber(2)가 끝날 때까지 기다린다.

전체 과정은 다음과 같다.

printNumber(3)
├─ 3 출력
└─ printNumber(2)
   ├─ 2 출력
   └─ printNumber(1)
      ├─ 1 출력
      └─ printNumber(0)
         └─ 종료

따라서 출력 결과는 다음과 같다.

3 2 1

함수 호출이 스택에 쌓였다가 역순으로 제거되는 과정을 나타낸 이미지이다.

호출된 함수가 종료되면 기다리고 있던 이전 함수로 돌아간다. 프로그램은 이렇게 돌아가야 할 위치와 각 함수의 지역변수 등을 호출 스택에 저장한다.

 

---

4. 재귀 호출 전에 출력하면 순차적으로 내려간다

다음 코드에서는 출력문이 재귀 호출문보다 앞에 있다.

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

    printf("%d ", n);
    printNumber(n - 1);
}

C 언어는 함수를 위에서 아래로 실행한다. 따라서 현재 숫자를 먼저 출력한 다음, 숫자를 1 줄여 자기 자신을 다시 호출한다.

입력이 3이라면 다음과 같이 실행된다.

printNumber(3)
1. 3을 출력한다.
2. printNumber(2)를 호출한다.

printNumber(2)
1. 2를 출력한다.
2. printNumber(1)을 호출한다.

printNumber(1)
1. 1을 출력한다.
2. printNumber(0)을 호출한다.

printNumber(0)
1. 종료한다.

결과는 다음과 같다.

3 2 1

이 경우 출력은 재귀 호출이 더 깊어지는 과정에서 발생한다. 즉, 계단을 내려가면서 숫자를 출력한다고 생각할 수 있다.

3 출력 → 한 층 내려감
2 출력 → 한 층 내려감
1 출력 → 한 층 내려감
0에서 종료

---

5. 재귀 호출 후에 출력하면 역순으로 올라온다

이번에는 출력문의 위치를 재귀 호출문 뒤로 옮긴다.

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

    printNumber(n - 1);
    printf("%d ", n);
}

입력이 3이라면 printf()를 바로 실행하지 않는다. 먼저 printNumber(n - 1)을 호출한다.

printNumber(3)
→ 출력을 미루고 printNumber(2)를 호출한다.

printNumber(2)
→ 출력을 미루고 printNumber(1)을 호출한다.

printNumber(1)
→ 출력을 미루고 printNumber(0)을 호출한다.

printNumber(0)
→ 종료한다.

printNumber(0)이 종료되면 기다리고 있던 함수로 돌아간다. 함수가 돌아가는 순서는 호출된 순서의 반대이다.

printNumber(1)로 돌아감 → 1 출력
printNumber(2)로 돌아감 → 2 출력
printNumber(3)으로 돌아감 → 3 출력

따라서 결과는 다음과 같다.

1 2 3

중요한 점은 함수 호출이 끝나도 이전 함수가 사라지지 않았다는 것이다. 이전 함수는 재귀 호출 다음 줄을 실행하기 위해 호출 스택에서 기다리고 있었다.

실행 흐름을 코드에 직접 표시하면 다음과 같다.

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

    printNumber(n - 1);  // 여기서 기다린다.
    printf("%d ", n);    // 호출이 끝나면 이곳으로 돌아온다.
}

재귀 호출 전에 작성한 코드는 내려가면서 실행되고, 재귀 호출 뒤에 작성한 코드는 돌아오면서 실행된다.

재귀 호출이 내려가는 과정과 함수가 다시 돌아오는 과정을 계단으로 표현한 이미지이다.

---

6. 두 출력 순서 비교하기

두 코드의 차이는 출력문의 위치뿐이다.

재귀 호출 전에 출력하는 경우

printf("%d ", n);
printNumber(n - 1);

현재 값을 먼저 출력하므로 다음 결과가 나온다.

3 2 1

재귀 호출 후에 출력하는 경우

printNumber(n - 1);
printf("%d ", n);

가장 깊은 호출까지 내려간 다음, 함수가 돌아오면서 출력하므로 다음 결과가 나온다.

1 2 3

이를 간단히 정리하면 다음과 같다.

출력문의 위치실행 시점입력이 3일 때 결과

재귀 호출 전	호출이 깊어지면서 실행	3 2 1
재귀 호출 후	함수가 돌아오면서 실행	1 2 3

---

7. 시간복잡도란 무엇인가

시간복잡도는 입력 크기가 증가할 때 연산 횟수가 얼마나 증가하는지를 나타낸다.

시간복잡도는 실제 실행 시간을 초 단위로 측정하는 개념이 아니다. 컴퓨터의 성능이나 실행 환경이 달라져도 알고리즘의 효율을 비교할 수 있도록 연산 횟수의 증가 형태를 표현한다.

대표적인 시간복잡도는 다음과 같다.

시간복잡도의미예시

O(1)	입력 크기와 관계없이 연산 횟수가 일정하다	배열의 특정 위치 확인
O(log n)	입력이 증가해도 연산 횟수가 천천히 증가한다	이진 탐색
O(n)	입력에 비례해 연산 횟수가 증가한다	1부터 N까지 출력
O(n²)	입력 크기의 제곱에 비례한다	이중 반복문
O(2ⁿ)	입력이 증가하면 연산 횟수가 매우 빠르게 증가한다	단순 피보나치 재귀

 

대표적인 시간복잡도별 연산 횟수의 증가 차이를 비교한 그래프이다.

 

---

8. 반복문의 시간복잡도

다음 반복문은 N번 실행된다.

for (int i = 1; i <= N; i++) {
    printf("%d ", i);
}

N이 3이면 출력문을 3번 실행하고, N이 100이면 출력문을 100번 실행한다.

입력 크기 N에 비례하여 작업 횟수가 증가하므로 시간복잡도는 다음과 같다.

O(N)

이 코드에서 사용하는 추가 변수는 i 정도이다. N이 커져도 필요한 변수의 개수가 증가하지 않는다. 따라서 추가 공간복잡도는 다음과 같다.

O(1)

---

9. 재귀함수의 시간복잡도

다음 재귀함수는 n을 1씩 줄이며 총 N번 호출된다.

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

    printf("%d ", n);
    printNumber(n - 1);
}

한 번 호출될 때마다 출력과 비교 같은 일정한 양의 작업을 수행한다.

이를 점화식으로 표현하면 다음과 같다.

T(N) = T(N - 1) + O(1)

이를 계속 전개하면 다음과 같다.

T(N)
= T(N - 1) + O(1)
= T(N - 2) + O(1) + O(1)
= T(N - 3) + O(1) + O(1) + O(1)
...
= T(0) + N × O(1)
= O(N)

따라서 이 재귀함수의 시간복잡도도 반복문과 동일한 O(N)이다.

반복문: O(N)
재귀함수: O(N)

출력문을 재귀 호출 전이나 후에 배치하더라도 실행 횟수는 달라지지 않는다. 출력 순서만 바뀌므로 두 코드의 시간복잡도는 모두 O(N)이다.

---

10. 시간복잡도가 같아도 메모리 사용량은 다르다

반복문과 재귀함수가 모두 O(N)의 시간복잡도를 가진다고 해서 완전히 같은 것은 아니다.

반복문은 일반적으로 하나의 함수 안에서 변수의 값만 변경한다.

for (int i = N; i >= 1; i--) {
    printf("%d ", i);
}

따라서 추가 공간복잡도는 보통 O(1)이다.

재귀함수는 호출할 때마다 현재 함수의 실행 상태를 호출 스택에 저장한다.

printNumber(3)
printNumber(2)
printNumber(1)

호출 깊이가 N까지 증가하므로 호출 스택에 저장되는 정보도 N에 비례하여 증가한다. 따라서 재귀함수의 추가 공간복잡도는 O(N)이다.

방식시간복잡도추가 공간복잡도

 

반복문	O(N)	O(1)
재귀함수	O(N)	O(N)

일반적으로 단순 반복 작업에서는 반복문이 메모리 면에서 더 효율적이다. 재귀함수는 호출할 때마다 함수 호출에 필요한 추가 작업도 발생하므로 실제 실행 속도에서도 반복문이 유리한 경우가 많다.

다만 재귀함수는 트리 탐색, 그래프 탐색, 분할 정복처럼 문제 자체가 재귀적인 구조를 가질 때 코드를 더 자연스럽고 간결하게 표현할 수 있다.

 

반복문과 재귀함수의 메모리 사용량 차이를 비교한 이미지이다.

---

11. 모든 재귀함수가 O(N)인 것은 아니다

재귀함수를 사용했다고 해서 시간복잡도가 항상 O(N)이 되는 것은 아니다. 한 번의 함수 호출에서 자기 자신을 몇 번 호출하는지와, 입력 크기가 어떻게 감소하는지에 따라 달라진다.

한 번씩 호출하는 경우

func(n - 1);

호출 횟수가 N에 비례하므로 일반적으로 O(N)이다.

입력을 절반씩 줄이는 경우

func(n / 2);

N → N/2 → N/4 → ... → 1로 감소하므로 일반적으로 O(log N)이다.

매번 두 번씩 호출하는 경우

func(n - 1);
func(n - 1);

각 호출이 다시 두 개의 호출을 만들기 때문에 호출 횟수가 급격히 증가한다. 일반적으로 O(2ⁿ)이 될 수 있다.

대표적인 예가 단순 재귀로 작성한 피보나치 함수이다.

int fibonacci(int n) {
    if (n <= 1) return n;

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

같은 값을 여러 번 중복 계산하므로 매우 비효율적이다. 따라서 재귀함수의 시간복잡도는 재귀 호출문의 개수와 입력 감소 방식을 함께 분석해야 한다.

---

12. 반복문과 재귀함수 중 무엇을 사용해야 하는가

단순히 숫자를 출력하거나 일정 횟수만큼 반복하는 작업에는 반복문이 더 적합한 경우가 많다.

for (int i = 1; i <= N; i++) {
    printf("%d ", i);
}

반복문은 동작이 직관적이고, 호출 스택을 추가로 사용하지 않는다.

반면 다음과 같이 문제 자체가 작은 문제로 계속 나뉘는 구조라면 재귀함수가 유용하다.

• 폴더 내부의 모든 파일을 탐색하는 작업
• 트리의 모든 노드를 탐색하는 작업
• 미로에서 경로를 찾는 작업
• 병합 정렬과 퀵 정렬
• 하노이의 탑
• 백트래킹 문제

재귀함수는 문제의 구조를 코드에 그대로 표현하기 쉽다는 장점이 있다. 그러나 종료 조건을 잘못 작성하거나 호출 깊이가 지나치게 커지면 스택 오버플로가 발생할 수 있으므로 주의해야 한다.

---

마무리

반복문과 재귀함수는 모두 반복 작업을 표현할 수 있지만 동작 방식은 다르다.

반복문은 한 함수 안에서 변수의 값을 변경하며 코드를 반복한다. 재귀함수는 자기 자신을 다시 호출하고, 기존 함수는 호출된 함수가 끝날 때까지 호출 스택에서 기다린다.

N부터 1까지 한 번씩 처리하는 단순한 코드라면 반복문과 재귀함수의 시간복잡도는 모두 O(N)이다. 하지만 반복문의 추가 공간복잡도는 O(1)이고, 재귀함수는 호출 스택을 사용하므로 O(N)이다.

재귀함수의 출력 순서는 출력문의 위치에 따라 달라진다.

printf("%d ", n);
printNumber(n - 1);

위 코드는 재귀 호출이 깊어지면서 출력하므로 3 2 1이 된다.

printNumber(n - 1);
printf("%d ", n);

위 코드는 가장 깊은 호출에서 돌아오면서 출력하므로 1 2 3이 된다.

결국 다음 한 문장으로 정리할 수 있다.

재귀 호출 앞의 코드는 내려가면서 실행하고, 재귀 호출 뒤의 코드는 돌아오면서 실행한다.