[C언어] 재귀적 거듭제곱 계산 구현

■ 재귀적 거듭제곱 계산 구현

C언어로 재귀(순환, recursion)적 거듭제곱 계산을 구현하면 다음과 같다. 

double power(double x, int n)
{
	if (n == 0) return 1;
	else if ((n % 2) == 0)
		return power(x * x, n / 2);
	else return x * power(x * x, (n - 1) / 2);
}

 

결과값을 볼 수 있는 전체 실행코드

#include <stdio.h>

double power(double x, int n)
{
	if (n == 0) return 1;
	else if ((n % 2) == 0)
		return power(x * x, n / 2);
	else return x * power(x * x, (n - 1) / 2);
}

int main()
{
	double a = power(3,4);
	printf("%f ", a);
}

n이 짝수라면 x^2를 먼저 계산한 후 n/2제곱한다. 홀수인 경우는 x^2를 (n-1)/2제곱하고 x를 곱한다.

여기서 유의할 점은 문제의 크기가 줄어든다. 처음에는 n승이었다가 n/2승으로 되고 또 n/4승으로 점점 문제의 크기가 줄어든다. 즉 순환호출을 한번 할 때마다 n의 크기가 절반씩 줄어들기 때문에 시간복잡도는 O(logn)이다.