[C言語]関数の再帰処理を用いた累乗と階乗を計算するプログラム[コード付]

どうも〜　シュモクザメです。
今日は大学の課題でよくある再帰を用いた累乗、階乗のプログラムを解説します！！

この解説において、関数のreturnなどはある程度理解した前提で進めていきます！
不安な方はこちらの記事を是非読んでください！

再帰処理とは何か？
コードの実装
まとめ

再帰処理とは何か？

まずはここから。
再帰処理というのは、
ある関数の中でその関数を呼び出す処理や構造のことです。
「再帰呼び出し」とも言いますね。

んー、、つまりループするってこと？？

まあそんな感じですね。
具体的に見てみましょう。

void R(void){
    printf("Hello\n");
    R();
}

この関数Rは実行すると、まずprintfでHelloを出力する。
そのあと関数R、つまり自分自身を呼び出します。

そしたらどうなるのかというと、
そのRの中でHelloを出力、そしてまたRを呼び出しますね。

そしてまたそのRの中で、、って感じで永遠にループしていきます。
この呼び出しが再帰処理ですね。

なのでこれを実行しちゃうとコンソールに無限にHelloが出てくる意味わからんプログラムってことです。
まあもちろん実用的ではないですよね。
本来の便利な使い方はどこかで再帰を止める処理を入れる必要があります。
ここら辺については次の累乗、階乗の関数の実装のところで解説します！

コードの実装

累乗の関数

とりあえずコードです。

int expo(int x, int n){
    int A;
    if(n==1){
        return x;
    }else{
        A = x*expo(x,n-1);
        return A;
    }
}

仮引数のxは元の値でnが指数です。
つまりこの関数ではx^nが値として返ってくるってことです。
短いんですがややこしいので一つづつやっていきましょう。

計算の結果を格納する変数

まずは最初のAについて。

int A;

このAは毎度の関数呼び出しの際に計算結果を格納して、
returnで一つ前の関数に渡すためにreturnされる変数です。

？？？？？

まあまだふんわりしていてよく分からないですよね。
一旦次に行きましょう。

else文

次にif-else文に入ります。
先にelse の処理から考えていきます。

else{
        A = x*expo(x,n-1);
        return A;
    }

if文がn==1なのでこのelse文はnが１ではない時に入ります。

処理の1行目は
xと、expoに(x,n-1)を渡して返ってくる値の積を、Aに代入する。という意味です。

ここで再帰しているね

そうですね、処理の順番としては
右辺を計算　→ 左辺に代入なのですが、
右辺の計算で再帰の関数呼び出しが入っている、
つまり呼び出した関数の計算を終わらさないと、この式の計算が完了しないってことですね。
つまりこんな感じ

このように続いていきますね。
上で述べた通りどこかでこの処理を止めなければいけません。
そこでif文を考えていきます!!

if文

ここはn==1の時に入る処理です。
処理は

if(n==1){
        return x;
    }

returnでxを返すだけですね。
つまりもう再帰しませんよ！！ってことです。

上のイメージ図で考えましょう。
再帰が続いて、nからn-kまで仮引数が小さくなったとして、
n-k==1ならばexpo(x,n-k)はif文の処理に入ります。
となると、returnがxとなるので、
expo(x,n-k)を呼び出したexpo(x,n-(k-1))のelse文の中の計算を進めることができます。

となるとexpo(x,n-(k-1))のreturn A = x*xまでが確定したので、
さらに一つ前のexpo(x,n-(k-2))の計算が進められますね、、とこんな感じでどんどん処理が戻っていきます。

戻って行く際にxをかけていくので最終的にexpo(x,n)に返ってきた時には、
xにxをn-1回かけたものがAに代入されて、それがreturnされます。

つまりこの関数の返り値がx^nということですね。
これで累乗の関数は完成です！

階乗の関数

コードです

int factorial(int n){
    int A=1;
    
    if(n==1){
        return 1;
    }else{
        A = n*factorial(n-1);
        return A;
    }
}

といってもほぼ解説することはありませんね。
かける数を１小さくしていく、つまり再帰の際に渡す引数を減らして、
引数が１になった時に折り返すようにreturn 1としているだけです。

まとめ

以上で解説は終了となります！
僕も初めは再帰処理がガチ意味不明でしたが、やはり便利ですし、
高速処理をやろうと思ったら必要なテクニックなので是非ここで覚えていってください！

この再帰処理を用いたコードについて解説した記事を下に貼っておくのでよければ読んでください！
ではまたー