C言語で再帰関数を使ってxのn乗を計算するプログラム

本記事では、C言語の再帰関数を利用して、実行時にユーザーが入力した値をもとに x の n 乗（xⁿ）を求める方法を解説します。

問題

実行時にユーザーから入力される x と n を受け取り、xⁿ の値を計算するプログラムを作成します。

解決策

C言語で再帰関数を使って 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 の性質に応じて処理を分岐させています。

• n が 1 の場合: x 自身をそのまま返す（再帰の終了条件）
• n が偶数の場合: x^n/2 を再帰的に求め、それを2乗することで計算量を削減できる
• n が奇数の場合: x × x^n-1 として、指数を1つ減らして再帰呼び出しを行う

アルゴリズム

再帰関数を使用して x の n 乗を求めるアルゴリズムの手順は以下の通りです。

ステップ1 − long int 型の変数を読み込む

ステップ2 − 関数プロトタイプを宣言する

ステップ3 − 関数を呼び出す

Xpown=power(x,n) ステップ5へ

ステップ4 − xpown を表示する

ステップ5 − 呼び出される関数の処理

  ステップ5.1 − if (n==1) の場合

    ステップ5.1.1 − return(x) を返す

  ステップ5.2 − そうでなく if (n%2 == 0) の場合

    ステップ5.2.1 − return (pow(power(x,n/2),2)) を返す /*nが偶数の場合*/

  ステップ5.3 − 上記以外の場合

    ステップ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 が出力されています。偶数の指数に対しては半分の指数で再帰計算を行うことで、効率よくべき乗を求められる点がこのアルゴリズムの特徴です。