LV05 재귀 함수에 대한 사실과 오해

C++ 함수 호출과 재귀함수

함수 복습하기

함수 호출의 기본 원리

함수가 호출될 때마다 새로운 **스택 프레임(Stack Frame)**이 생성됩니다. 각 함수는 독립적인 메모리 공간을 가지며, 매개변수와 지역변수들이 이 공간에 저장됩니다.

함수 호출 과정 시각화

함수 호출 메커니즘:

매개변수 복사: main의 x값(3)이 BBQ 함수의 매개변수 x로 복사

독립적 실행: BBQ 함수 내부에서 x++은 복사된 값만 변경

원본 보존: main 함수의 x는 여전히 3

함수 종료: BBQ 함수 종료 후 main으로 복귀

return 키워드의 중요성

return 키워드를 통해 나를 호출하기 전에 함수로 실행 프로세스를 넘겨준다는 의미였다.

함수마다 공간이 다른 공간이기 때문에 같은 지역변수 이름이 허용된다.

#include <iostream>
using namespace std;

void BBQ(int x)
{
    cout << "BBQ 함수 내부 x: " << x << endl;  // 3
    x++;
    cout << "BBQ 함수 x++ 후: " << x << endl;  // 4
}

int main()
{
    int x = 3;
    cout << "main 함수 x: " << x << endl;      // 3

    BBQ(x);

    cout << "BBQ 호출 후 main x: " << x << endl; // 여전히 3

    return 0;
}
C++
복사

재귀 함수 (Recursive Function)

재귀 함수의 정의

대부분의 인터넷 설명을 보다보면 재귀함수는 자기 자신을 호출하는 것이라고 표현한다.

하지만 실상은 반은 맞고 반은 틀린 말이다. 해당 표현으로 이해를 하게되면 결국 같은 함수로 오해하여 이해 함수 없기 때문이다.

재귀함수란 흔히 나 자신을 호출하는 함수라고 많이들 이야기 하지만 실제로는 코드가 재활용 되어 같은 이름의(다른함수)를 또 호출하는 것이다.

결론적으로 코드만 같고 다른 함수로 이해 하면 구조를 파악하기 쉽다.

재귀 함수의 메모리 구조

재귀 함수는 **스택(Stack)**이라는 메모리 구조를 사용합니다:

장점:

•

변수를 여러 만들 필요가 없다.

•

예들들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드로 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있습니다

while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해집니다.

단점:

•

지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야합니다

•

그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어집니다

함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 됩니다.

기본적인 재귀 함수 예제

#include <iostream>
using namespace std;

// ABC -> test -> main 순서로 배워야한다
// 가장 나중에 들어온 데이터가 가장 먼저 빠져나가는 것 = stack

// 재귀함수를 통한 나 자신을 호출하는 함수라고 많이들 하지만
// 실제로는 코드가 재활용되어 똑같은 이름의 다른 함수를 호출하는 것이다.
// 5. main -> test -> test -> test .......
// 재귀에서 스택이 쌓이는 것이다.
// 아래의 코드를 r5 하면 'Stack Overflow' 표시가 나온다

void test(int x)
{
    // 무한정 호출되는 함수를 방지해야 하는 게 급선무이다.
    // test(x);

    // 아래의 함수를 호출함 4025번까지 호출하고나서 stack Overflow 된다
    // test(x + 1);

    if (x == 3)
    {
        return;
        // test(2) 로 돌아감 -> test(1) -> ... main 으로 돌아감
    }

    test(x + 1);
    cout << x << endl;
}

int main()
{
    test(0);

    return 0;
}
C++
복사

재귀 함수 실행 과정 상세 분석

스택 프레임 분석:

호출 순서: main(0) -> test(0) -> test(1) -> test(2) -> test(3)
반환 순서: test(3) return -> test(2) -> test(1) -> test(0) -> main
Plain Text
복사

실행 흐름:

test(0) 호출: x=0, x≠3이므로 test(1) 호출

test(1) 호출: x=1, x≠3이므로 test(2) 호출

test(2) 호출: x=2, x≠3이므로 test(3) 호출

test(3) 호출: x=3, x==3이므로 return 실행

test(2)로 복귀: cout << 2 실행 후 종료

test(1)로 복귀: cout << 1 실행 후 종료

test(0)로 복귀: cout << 0 실행 후 종료

출력 결과: 2 1 0

배열을 이용한 재귀 함수

#include <iostream>
using namespace std;

int arr[5] = { 5, 7, 1, 2, 3 };

void test(int x)
{
    if (x == 5)
    {
        return;
    }

    cout << arr[x] << " ";
    test(x + 1);
    cout << arr[x] << " ";
}

int main()
{
    test(0);

    return 0;
}
C++
복사

실행 과정:

test(0): arr[0]=5 출력, test(1) 호출

test(1): arr[1]=7 출력, test(2) 호출

test(2): arr[2]=1 출력, test(3) 호출

test(3): arr[3]=2 출력, test(4) 호출

test(4): arr[4]=3 출력, test(5) 호출

test(5): return 실행

test(4)로 복귀: arr[4]=3 출력

test(3)로 복귀: arr[3]=2 출력

test(2)로 복귀: arr[2]=1 출력

10.

test(1)로 복귀: arr[1]=7 출력

11.

test(0)로 복귀: arr[0]=5 출력

출력 결과: 5 7 1 2 3 3 2 1 7 5

재귀함수를 이용한 배열 순회

#include <iostream>
using namespace std;

// 문제
// 출력결과 : 0 1 2 3
int arr[5] = { 5, 7, 1, 2, 3 };

void test(int x)
{
    // 무한정 호출되는 함수를
    // 방지해야 하는 게 급선무이다.
    if (x == 3)
    {
        return;
    }

    cout << arr[x] << endl;
    test(x + 1);
}

int main()
{
    test(0);

    return 0;
}
C++
복사

순방향 출력 결과: 5 7 1 (arr[0], arr[1], arr[2])

재귀 함수의 다양한 활용

팩토리얼 계산

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

    return n * factorial(n - 1);
}

// factorial(5) = 5 * factorial(4) = 5 * 4 * 3 * 2 * 1 = 120
C++
복사

스택 오버플로우 방지

스택이 넘어가면 프로그램이 강제 종료 될수 있기에 예외처리를 넣어주는 것이 실무에서는 좋다.

void safeRecursion(int x, int maxDepth = 1000)
{
    if (x >= maxDepth)  // 최대 깊이 제한
    {
        cout << "Maximum recursion depth reached!" << endl;
        return;
    }

    // 재귀 로직
    safeRecursion(x + 1, maxDepth);
}
C++
복사

꼬리 재귀 최적화(중요사항 X 읽고 이런게 있구나 하고 넘어가세요.)

*꼬리 재귀(Tail Recursion)*

// 일반 재귀 (비효율적)
int factorial(int n)
{
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 곱셈 후 반환
}

// 꼬리 재귀 (효율적)
int factorialTail(int n, int result = 1)
{
    if (n <= 1) return result;
    return factorialTail(n - 1, n * result);  // 즉시 재귀 호출
}
C++
복사

재귀 vs 반복문 비교

성능 비교

특성	재귀 함수	반복문
메모리 사용	많음 (스택 프레임)	적음 (지역변수만)
속도	느림 (함수 호출 오버헤드)	빠름
코드 가독성	높음 (직관적)	보통
디버깅	어려움	쉬움
스택 오버플로우	위험	안전

사용 권장 사항

재귀 함수를 사용하기 좋은 경우:

•

트리나 그래프 탐색

•

분할 정복 알고리즘

•

수학적 점화식 구현

•

코드 가독성이 중요한 경우

반복문을 사용하기 좋은 경우:

•

단순 반복 작업

•

성능이 중요한 경우

•

메모리 사용량을 줄여야 하는 경우

•

깊은 재귀가 예상되는 경우

재귀 함수는 복잡한 문제를 간단하게 표현할 수 있는 강력한 도구이지만, 성능과 메모리 사용량을 고려하여 적절히 사용해야 합니다. 특히 스택 오버플로우를 방지하기 위한 종료 조건 설정이 매우 중요합니다.

“강의는 많은데, 내 실력은 왜 그대로일까?”

혼자서 공부하다 보면

이런 생각 들지 않으셨나요?

•

강의는 다 듣고도 직접 코드는 못 짜겠고,

•

복습할 땐 어디서부터 다시 시작해야 할지 막막하고,

•

질문하려 해도 물어볼 사람이 없고,

•

유튜브 영상도 정답만 보고 따라 치는 느낌…

그렇다면 지금이 바로

“나만을 위한 코칭”이 필요한 순간입니다.

당신도 할 수 있습니다.

지금 멤버십을 넘어, 코칭에 도전해보세요.

수많은 수강생들이 얌얌코딩 코칭으로 넥슨, 크래프톤, NC 등 입사에 성공했습니다.

프리미엄 코칭 안내 바로가기

또는 카톡 오픈채팅: 얌얌코딩 상담방

지금도 코딩을 ‘따라 치기만’ 하고 계신가요?

이젠 혼자 설계하고, 스스로 코딩하는 법을 배워야 할 때입니다.

얌얌코딩이 옆에서 함께하겠습니다.