Jiyeon Kang

It’s my CV

3 minute read

알고리즘 수업시간에 재귀호출의 효율성에 대해 배웠는데 따로 정리하는 것이 좋을 듯 하여 정리한다! 개인적으로 이해를 돕기위해 내용을 추가하였다 우선 프로그램의 실행방식에 대해 알아보도록 하자



일반적인 프로그램 실행 방식

프로그램의 실행방식

• 프로그램이 실행되면, 하드디스크에 저장된 소스코드가 필요한 부분만 메인 메모리에 적재되어 실행된다 • 하지만 프로그램이 길면, 한 번에 모든 코드를 메모리에 올릴 수 없고, 필요한 부분만 CPU가 실행할 때마다 메모리에 올리고 내리는 과정을 반복한다


예를 들어, 실행할 코드가 [p1][p2][p3]...[p6]처럼 쭉 있다고 가정하자

  • CPU는 먼저 [p1]을 실행하고, 다음 필요한 [p2]를 메모리에 올려 실행한다
  • 만약 [p5]에서 새로운 라이브러리를 불러와야 하면, 하드디스크에서 해당 코드를 가져오는 디멘드 페이징(Demand Paging)이 발생한다
  • 이 과정에서 메모리 접근 속도보다 하드디스크의 속도가 훨씬 느리기 때문에 실행 속도가 떨어지게된다

💡 디멘드 페이징(Demand Paging)과 성능 저하 • 디멘드 페이징이란, 메모리에 로드되지 않은 코드를 실행할 때, 필요할 때마다 하드디스크에서 읽어와 메모리에 적재하는 방식임 • 이 과정이 발생하면 CPU는 코드가 로드될 때까지 대기해야 하므로 실행 속도가 느려짐 • 즉, 실행 중인 코드가 계속 메모리를 들락날락하면 캐시 효율이 떨어지고 성능이 저하됨



재귀함수가 효율적인 이유

재귀함수는 자기 자신을 호출하는 방식으로 동작하는데, 이 방식이 디멘드 페이징을 최소화하여 실행 속도를 빠르게 만듦


이유 1: 코드가 연속적으로 실행됨

재귀호출은 같은 함수를 반복해서 호출하는 구조이므로, 이미 메모리에 올라간 함수 코드가 계속 실행됨 즉, 추가적인 코드 로드(디멘드 페이징)가 거의 발생하지 않음


이유 2: 스택 프레임을 활용하여 메모리 효율적 사용

재귀함수는 내부적으로 스택(Stack) 메모리를 사용하여 함수 호출을 관리함
반복문보다 메모리를 많이 사용할 수도 있지만, 코드가 일정하게 유지되므로 메모리 로딩 측면에서 CPU 캐시 활용이 최적화됨


이유 3: 실행 흐름이 단순하여 분기 부담이 적음

재귀는 실행 흐름이 단순하여, 새로운 함수를 찾거나 다른 파일에서 코드 불러오는 작업이 거의 발생하지 않음 즉, 실행 도중 새로운 코드 로드로 인한 병목 현상이 줄어듦



재귀함수가 비효율적인 이유

스택(Stack)과 함수 호출

함수를 호출할 때, 스택이 어떻게 동작하는가?

• 스택(Stack)은 함수가 호출될 때마다 호출 정보를 저장하는 영역 • 함수를 실행하면 스택 프레임(Stack Frame)이 생성되고, 함수의 지역 변수 (Local Variable), 복귀 주소 (Return Address, 실행이 끝나면 돌아갈 곳) 등이 저장됨 • 함수 실행이 끝나면, 스택에서 pop되어 원래 위치로 돌아감


스택 메모리에서 함수 호출 과정

예제 코드를 보고 함수가 실행될 때 어떻게 쌓이고, pop되는지 보자

void A() {
    int i = 3;
    int j = 2;
}

void B() {
    int a = 3;
    C();
}

void C() {
    int b = 2;
    return;
}


위 코드가 실행될 때 스택 메모리 변화를 보면:

// 1) B() 실행 → 스택에 B() 정보 저장 
| B() - 지역변수 a=3, 복귀주소 |
|------------------------------|

// 2) C() 실행 → 스택에 C() 정보 저장
| C() - 지역변수 b=2, 복귀주소 |
| B() - 지역변수 a=3, 복귀주소 |
|------------------------------|

// C() 실행 완료 → 스택에서 pop됨 (C() 함수가 끝나고 B()로 복귀)
| B() - 지역변수 a=3, 복귀주소 |
|------------------------------|

// B() 실행 완료 → 스택에서 pop됨 (B() 함수가 끝나고 메인 함수로 복귀)
(스택이 비워짐)


=> 스택은 LIFO(Last In First Out) 구조이므로, 실행이 끝난 함수부터 차례대로 제거됨


재귀호출의 문제점

• 재귀 호출을 할 때마다 새로운 스택 프레임이 추가됨 • 즉, 반복 호출이 많아지면 스택 메모리가 빠르게 차버려 공간 낭비가 심해짐

void recursiveFunction(int n) {
    if (n == 0) return;
    recursiveFunction(n - 1);
}


이 함수가 recursiveFunction(5)로 실행된다면?

스택 변화: • recursiveFunction(5) 실행 → n=5 저장
• recursiveFunction(4) 실행 → n=4 저장
• recursiveFunction(3) 실행 → n=3 저장
• recursiveFunction(2) 실행 → n=2 저장
• recursiveFunction(1) 실행 → n=1 저장
• recursiveFunction(0) 실행 → 종료

이후 n=1부터 차례로 pop되어 스택에서 사라진다


문제점:

  • 만약 n=1000000 같은 큰 값이 들어오면?
  • 스택 오버플로우(Stack Overflow) 발생! (메모리가 꽉 차서 프로그램이 강제 종료됨.)


공간 복잡도 문제

  • 반복문(for or while)을 사용하면 O(1) 메모리 사용
  • 하지만 재귀는 O(n) 메모리를 사용 (즉, n이 커질수록 공간 낭비가 심해짐)



재귀호출의 효율적인 해결 방법

꼬리 재귀(Tail Recursion) 최적화

  • 일부 컴파일러는 꼬리 재귀(Tail Recursion Optimization, TCO)를 지원함
  • 스택을 덜 사용하게 최적화(컴파일러가 반복문으로 변환 가능)해서, 공간 복잡도를 줄여줌
void tailRecursive(int n, int result) {
    if (n == 0) return;
    tailRecursive(n - 1, result + n);
}


반복문으로 변경하기

  • 재귀를 쓰지 않고 반복문으로 변환하면 공간 효율성이 훨씬 좋아짐
  • 공간 복잡도 O(1), 메모리 절약!
void loopFunction(int n) {
    for (int i = n; i > 0; i--) {
        // 계산 수행
    }
}



결론

재귀 호출의 장점

  • 논리적으로 코드를 직관적으로 만들 수 있음
  • 일부 문제(DFS, 피보나치, 분할 정복 등)에서는 재귀가 자연스러움
  • 디멘드 페이징이 적어 CPU 캐시 활용도가 높아질 수 있음


재귀 호출의 단점

  • 스택 메모리를 많이 사용하여 공간 복잡도가 높아질 수 있음.
  • n이 클 경우 스택 오버플로우 발생 가능
  • 반복문으로 대체 가능한 경우가 많음


정리하면?

  • 재귀가 항상 효율적인 것은 아니다.
  • 시간 복잡도는 최적화될 수 있지만, 공간 복잡도가 커질 수 있음
  • 꼬리 재귀(TCO)나 반복문 변환을 고려해야 함!
  • 일반적인 코드 실행은 디멘드 페이징 때문에 속도가 느려질 수 있음
  • 재귀호출은 메모리에 로드된 함수 코드가 계속 실행되므로 추가적인 코드 로딩이 필요 없음.
  • 따라서 재귀호출은 CPU와 메모리 활용 측면에서 효율적임
  • 단, 너무 깊은 재귀는 스택 오버플로우(Stack Overflow)를 일으킬 수 있으므로 주의해야 함!

You may also enjoy