c言語 アルゴリズムの説明をしてください。

Question

大学のCのプログラミングの課題でて、一応できたのですが、なぜこういうコード(アルゴリズム)なのかがわかりません。
問題は、文字’L’がl個、’R’がr個で構成される文字列をすべて表示する関数を作成する。こ こで、l と r は非負整数でキーボードから入力し、l + r ≤ 8 としてよい (高々8 文字が入 る配列 str[9] を 1 つ用意すると良い)。キーボードから非負整数 l, r(ただし l + r ≤ 8) を入力すると上記の関数を呼び出し、文字列を表示するプログラムを作成せよ。(参考: ’L’ を選べれば選んで、残り l − 1 個と r 個の文字列作成。同様に’R’ を選べれば選ん で · · ·。と両方行えばすべて行ったことになる。)　です。

コードのわからない部分は、関数func()の引数にi,l,r,strがありますが、関数を使う時に、引数として、0を渡しているところです。なぜ、0なのでしょうか？また、関数func()ないのif文での処理でなぜ、問題文のようなコードがかけるのでしょうか？わかる方いらっしゃましたら、よろしくお願いします！

#include <stdio.h>

void func(int i, int l, int r, char *str);

int main(void){
    int l,r;
    char buf[8+1];
    printf("Input two non-neg. intergers ,l and r:");
    scanf("%d%d",&l,&r);
    // printf("l:%d",l);
    // printf("r:%d",r);
    func(0,l,r,buf);
}

void func(int i, int l, int r, char *str){
    if(l + r == 0){
        str[i] = '\0';
        printf("%s\n", str);
    }
    if(l > 0){
        str[i] = 'L';
        func(i + 1, l - 1, r, str);
    }
    if(r > 0){
        str[i] = 'R';
        func(i + 1, l, r - 1, str);
    }
 }

Comments

[KoichiSugiyama]

再帰関数という言葉は習いましたか？この問題はその再帰関数を使っています。デバッガで一行ずつ追ってみると動作が理解しやすいと思いますが、実際にステップ実行して判らないところがあれば、再度質問されてはどうでしょうか。

[Kazuma_3]

わかりました。デバック環境の構築からやってみます。

Answer 1

なぜ、0なのでしょうか？

bufの先頭から使うから0を渡しているのでしょう。

また、関数func()ないのif文での処理でなぜ、問題文のようなコードがかけるのでしょうか？

「再帰的処理」の概念を学びましょう。
高校数学で学んだ「数学的帰納法」を覚えていますか？

Comments

[Kazuma_3]

その再帰的処理がわからなかったため質問をしました。

[otn]

簡単に言うと、nの時の処理をn-1の時の処理に任せることです。
階乗計算を再帰処理で求める方法は分かりますか？
f(n) = n * f(n-1) ・・・ n>0 のとき
f(0) = 1

[Kazuma_3]

はい、わかります。
数学みたいな計算とかの再帰的処理はわかりやすいのですが、今回の問題みたいになると…

Answer 2

関数を使う時に、引数として、0を渡しているところです。なぜ、0なのでしょうか？

配列の先頭は0番目です。まずは0文字目を決める必要があります。