C Academy · 강의

고전적인 재귀 문제

팩토리얼과 피보나치를 배워 보세요.

고전적인 재귀 문제은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

대표적인 문제

일부 문제는 자연스럽게 재귀로 표현할 수 있습니다. 대표적인 문제를 배우면 재사용할 수 있는 패턴을 익힐 수 있습니다.

이 단원에서는 팩토리얼, 피보나치 수, 자릿수의 합, 최대공약수, 출력 순서 뒤집기를 다룹니다.

팩토리얼

n의 팩토리얼은 n에 n-1의 팩토리얼을 곱한 값이며, 1!은 1입니다.

이는 명확한 기저 사례와 하나의 재귀 호출을 갖춘 전형적인 재귀입니다.

#include <stdio.h>

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

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

피보나치 수

각 피보나치 수는 바로 앞의 두 수를 더한 값입니다. 재귀 정의에는 fib(0)=0과 fib(1)=1이라는 두 개의 기저 사례가 필요합니다.

이 방식은 단계마다 두 번 호출합니다.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

피보나치 실행하기

다음은 완전한 프로그램입니다. fib(10)은 55를 출력해야 합니다.

이 단순한 방식은 같은 작업을 반복하므로 n이 크면 느립니다.

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("%d\n", fib(10));
    return 0;
}

자릿수의 합

수의 각 자릿수를 더하려면 n % 10으로 마지막 자릿수를 구하고, n / 10으로 나머지에 대해 재귀를 수행합니다.

n이 0이 되면 재귀가 끝납니다.

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

자릿수의 합 실행하기

1234의 합은 1+2+3+4 = 10입니다. 완전한 프로그램으로 확인해 보겠습니다.

#include <stdio.h>

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(1234));
    return 0;
}

최대공약수

유클리드 알고리즘은 자연스럽게 재귀로 표현됩니다. a와 b의 GCD는 b와 a % b의 GCD와 같습니다.

b가 0이 되면 a가 답입니다.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

GCD 완전한 프로그램

48과 18의 GCD는 6입니다. 이 프로그램은 그 값을 출력합니다.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void) {
    printf("%d\n", gcd(48, 18));
    return 0;
}

수 뒤집기

재귀는 출력 순서를 제어하는 데도 사용할 수 있습니다. 재귀를 수행한 후 마지막 자릿수를 출력하면 처리 순서가 자연스럽게 뒤집힙니다.

이 도우미 함수는 재귀를 사용하여 수의 각 자릿수를 한 줄씩 출력합니다.

#include <stdio.h>

void print_digits(int n) {
    if (n == 0) return;
    print_digits(n / 10);
    printf("%d ", n % 10);
}

int main(void) {
    print_digits(729);
    printf("\n");
    return 0;
}

거듭제곱 함수

밑을 지수만큼 거듭제곱하는 연산도 재귀적으로 표현할 수 있습니다. base^exp는 base에 base^(exp-1)를 곱한 값과 같습니다.

기저 사례는 지수가 0인 경우이며, 이때 1을 반환합니다.

long power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

다시 사용할 패턴

공통된 형태에 주목해 보십시오. 먼저 기저 사례를 확인한 다음, 현재 단계의 값과 더 작은 호출의 결과를 결합합니다.

이 패턴을 발견하면 많은 문제를 짧은 재귀 함수로 작성할 수 있습니다.

빠른 확인

올바른 기저 사례를 고르십시오.

요약

팩토리얼, 피보나치, 자릿수 합, GCD, 거듭제곱은 모두 하나의 재귀 패턴을 공유합니다. 기저 사례를 처리한 다음, 현재 값과 더 작은 하위 문제의 결과를 결합합니다.

이러한 틀은 다른 많은 작업에도 그대로 적용할 수 있습니다.

자주 묻는 질문

“고전적인 재귀 문제” 강의는 무료인가요?

네 — “고전적인 재귀 문제” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“고전적인 재귀 문제”에서 뭘 배우나요?

팩토리얼과 피보나치를 배워 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

“고전적인 재귀 문제” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← C Academy(으)로 돌아가기