C 언어 재귀 함수를 활용해 x의 n제곱 값을 계산하는 프로그램

문제 개요

xⁿ의 값을 계산하는 것이 목표입니다. 여기서 x와 n은 모두 실행 시점에 사용자가 직접 입력하는 값입니다.

해결 방법

C 언어에서 재귀 함수(recursive function)를 사용하여 x의 n제곱 값을 구하는 방법은 다음과 같습니다.

xⁿ을 구하는 핵심 로직은 아래와 같습니다.

//함수 호출부:
Xpow = power(x, n);
//호출되는 함수:
if (n == 1)
    return(x);
else if (n % 2 == 0)
    return (pow(power(x, n/2), 2)); /* n이 짝수인 경우 */
else
    return (x * power(x, n-1));

동작 원리

이 알고리즘은 재귀 호출을 통해 문제를 점진적으로 축소합니다. 지수 n이 1이 되면 밑값 x를 그대로 반환하며 재귀가 종료됩니다. n이 짝수라면 x^n/2를 먼저 구한 뒤 제곱하여 효율적으로 계산하고, n이 홀수라면 x를 한 번 곱한 후 나머지 지수에 대해 재귀 호출을 수행합니다.

알고리즘

재귀 함수를 이용해 x의 n제곱 값을 생성하기 위한 알고리즘은 다음 단계를 따릅니다.

1단계 − long int형 변수를 선언하고 값을 읽어 들입니다.

2단계 − 함수 원형(prototype)을 선언합니다.

3단계 − 함수를 호출합니다.

Xpown = power(x, n) → 5단계로 이동

4단계 − xpown 값을 출력합니다.

5단계 − 호출되는 함수의 처리 과정:

  5.1단계 − if (n == 1)

    5.1.1단계 − return(x)

  5.2단계 − else if (n % 2 == 0)

    5.2.1단계 − return(pow(power(x, n/2), 2)); /* n이 짝수인 경우 */

  5.3단계 − else

    5.3.1단계 − return(x * power(x, n-1)); /* n이 홀수인 경우 */

전체 프로그램

다음은 재귀 함수를 사용하여 x의 n제곱 값을 생성하는 C 프로그램입니다.

#include <stdio.h>
#include <math.h>
void main(){
    long int x, n, xpown;
    long int power(int x, int n);
    printf("Enter the values of X and N: \n");
    scanf("%ld %ld", &x, &n);
    xpown = power(x, n);
    printf("X to the power N = %ld\n", xpown);
}
/* X의 N제곱을 계산하는 재귀 함수 */
long int power(int x, int n){
    if (n == 1)
        return(x);
    else if (n % 2 == 0)
        return (pow(power(x, n/2), 2)); /* n이 짝수인 경우 */
    else
        return (x * power(x, n-1)); /* n이 홀수인 경우 */
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter the values of X and N:
5 4
X to the power N = 625

위 예시에서는 x = 5, n = 4를 입력했으며, 프로그램은 5⁴ = 625를 정확히 계산하여 출력합니다. 짝수 지수에 대해 중간 결과를 제곱하는 방식을 활용하기 때문에 단순 반복 곱셈보다 적은 수의 재귀 호출로 결과를 얻을 수 있다는 장점이 있습니다.