56章再帰呼び出し - (void*)Pないと

http://www.geocities.jp/ky_webid/c/056.html

自分で定義した関数の中で、その定義した関数を再度呼ぶ。

これを再帰といいます。

ある種無限ループですね。どこで終了させるかがわかりにくいのが特徴です。

問題1

100から引数の値まで、1ずつ減らしながら画面に表示していく再帰関数を作って下さい。

初再帰プログラムですね。

void print_rec (int num) {
    if ( num <= 100 ) {
        printf("%d ",num);
        print_rec(num+1);
    }
    return ;
}

int main () {
    print_rec(90);
    return 0;
}

$ main
90 91 92 93 94 95 96 97 98 99 100

とりあず、逆ですが引数から100までならできました。

しかし問題は100から引数まで減らしながら表示なのでちょっと難しいですね。

いろいろがんばった結果こうなりました。

void print_rec (int num) {
    static int start = 100;
    if ( num <= 100 ) {
        printf("%d ",start--);
        print_rec(num+1);
    }
    else {
        start = 100;
    }
    return ;
}

int main () {
    print_rec(90);
    puts("");
    print_rec(88);
    return 0;
}

$ main
100 99 98 97 96 95 94 93 92 91 90
100 99 98 97 96 95 94 93 92 91 90 89 88

static変数で100を持っておき、それを減算しながら表示しました。

numの条件が100を超えたときにstartの値も初期値の100に戻しています。

こうしないと二度目のprint_rec呼び出しした際に一度目に呼び出した時の値から始まってしまうからです。

$ main
100 99 98 97 96 95 94 93 92 91 90
89 88 87 86 85 84 83 82 81 80 79 78 77
↑続きからカウントされてしまっている！

でもこれであってるんでしょうか・・・自信ないです。

多分もっとちゃんとしたやり方があると思います。static使わなくても。

答え合わせ

void print_rec(int num){
    if( num <= 100 )  /* 100まで再帰呼び出し */
    {
        print_rec( num+1 );
        printf( "%d\n", num );  /* 再帰呼び出しから戻ってきたときに表示 */
    }
}

なななななるほどぉ！！！！再帰呼び出しして戻ってきてから表示させればいいわけですか。

確かにこれで完璧ですね。numが100に達するまでは再帰呼び出しになるのでprintfは実行されないというわけです。

そして再帰から抜けるタイミングでひとつずつ減りながら表示されるわけなんですね。素晴らしいです。

問題2

階乗を求める再帰関数を作って下さい。階乗とは、ある値から１までの各数値を全て掛け合わせるというものです。例えば、５の階乗は、５×４×３×２×１＝１２０となります。

階乗！階乗は以前実装したことがあります（参考：累乗、階乗 - (void*)Pないと）

あの時は再帰呼び出しを習っていなかったためfor文で実装しました。

今回はそれを再帰で実現するというわけですね。やってみます。

unsigned int factorial (int num) {
    if ( num < 2 ) {
        return 1;
    }
    return num * factorial(num-1);
}

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

$ main
120
3628800

できました。今度はかなりうまくいったと思います。

引数の値と、引数-1した値を再帰して帰ってきた戻り値をかけるだけでOKです。

終了条件は引数のnumが1以下になった場合、再帰をやめて1を返してあげれば、numかける1になるので階乗結果の値を壊さずに戻り値を返すことができるということです。

答え合わせ

合ってました。

問題3

次のようなint型の配列があります。
int array[11];
この配列を次のように初期化する再帰関数を作って下さい。
5 4 3 2 1 0 1 2 3 4 5
←添字0　　　添字10→

難しそうですね・・・。というか再帰の処理って基本的に難しいです。

#include <stdlib.h>

void setarray(int *array,size_t size,int set) {
    int num = size / 2;
    
    if ( 0-num > set ) {
        return;
    }
    
    *array++ = abs(set);
    setarray(array,size,set-1);
}

int main () {
    int array[11];
    int i;
    
    setarray(array,11,5);
    
    for(i=0;i<11;++i) {
        printf("%d ",array[i]);
    }
    
    return 0;
}

$ main
5 4 3 2 1 0 1 2 3 4 5

めちゃくちゃ難しかったです。めちゃくちゃ悩みました。

今はこれ以上のものが出そうにないです。setarrayの引数に配列のサイズと初期値を渡してますが、これをせずに再帰だけでできるんでしょうか。

一応配列のサイズはsetarray内部でもsizeofで動的に算出はできますがセットする初期値だけはどうしても省けなかったです・・・。

答えあわせが楽しみです。

答え合わせ

うわー全然違ったｗ

考え方も何もかも違いましたね・・・。

解答例では配列の中央を基点として、そこから右と左を走査していき値を設定していっています。

でもこれ再帰は再帰なんだけどひとつの関数で再帰しないといけないと思っていたのでこの発想にはならなかったですね。

まぁ引数に右を見るか、左を見るかのフラグを渡せばひとつの関数でもできるといえばできますが、やはり可読性の観点から関数はわけたほうが見やすそうです。

当然のことながら、こんな処理を再帰でする必要性はまったくありません。ループだけで簡単に実現できるなら、再帰を使うべきではありません。

このようなforで簡単に実現できる処理をわざわざ再帰でやる必要はないということですね。

変に覚えたてで可読性の下がるコードを書かないように気をつけましょう。