C와 C++의 재귀와 호출 스택 C/C++ 온라인 실행

소개

재귀는 문제를 같은 종류의 더 작은 문제로 줄여서 푸는 방법입니다. 모든 재귀 함수에는 기저 사례(base case)가 있어야 하고, 호출할 때마다 그쪽으로 다가가야 합니다. 그렇지 않으면 프로그램이 함수를 끝없이 다시 호출합니다.

핵심 정리

빈 입력, 요소 하나, 중복 값, 이미 정렬된 데이터로 테스트하세요.
먼저 코드가 올바르게 동작하게 만든 다음 최적화하세요.
실제 코드에서는 표준 라이브러리의 이미 만들어진 함수를 우선 쓰세요.

동작 원리 보기

한 단계를 눌러 각 호출을 따라가세요. 새 호출은 콜 스택에 쌓이고, 각 호출은 자신을 부른 곳에 값을 돌려줍니다.

C와 C++ 코드 예제

C

실행 →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

실행 결과

C++

실행 →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

실행 결과

C와 C++ 비교

factorial 함수는 number가 2보다 작으면 1을 돌려주고(기저 사례), 그렇지 않으면 number * factorial(number - 1)을 돌려줍니다. 호출할 때마다 호출 스택(call stack)에서 공간을 조금씩 더 쓰므로 알고리즘은 O(n) 시간과 O(n) 스택을 씁니다. C++ 버전은 함수에 constexpr을 붙여 컴파일할 때 값을 계산할 수 있게 합니다. 입력이 클 때는 데이터를 검사해야 하고, 보통 재귀보다 반복문을 쓰는 것이 좋습니다.

C

반복문, 포인터, 길이, 임시 버퍼를 모두 명시적으로 작성합니다.

C++

반복자와 표준 알고리즘이 처리 방식과 데이터를 저장하는 방식을 분리합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

종이에 비교 과정을 하나씩 따라가 보세요.
중복 값과 아주 크거나 작은 값으로 테스트해 보세요.
직접 작성한 코드의 실행 시간을 재고 표준 라이브러리와 비교해 보세요.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지