再帰関数の作り方のコツが少しわかった気がしたメモ

May 05, 2020

学校の課題やってるときに、なんとなく再帰関数を作るときの考え方がわかったような気がしたので、メモしておきます。
技術的な話というよりは、思考のプロセスの話です。
今回は、重複なしの組み合わせを全列挙するプログラムで考えてみます。言語はCです。

まず再帰しないでどう書くか考える

まず再帰を使わず、普通にfor文で書いたらどうなるかってのをシミュレーションしてみます。
具体的な方がわかりやすいので、とりあえず ${}_7 \mathrm{C} _3$ で考えてみましょう。

for(i=0;i<5;i++){
  for(j=i+1;j<6;j++){
    for(k=j+1;k<7;k++){
      printf("%d%d%d\n",i,j,k);
    }
  }
}

こんな感じですかね。具体的な値なら、こういうfor文で書けますよね。
でも、実際に渡される値は7,3みたいな具体的な値じゃなくて、n,rなど不確定なので、for文では書けない。
なので次のステップです。

抽象化する

さっきのfor文を抽象化していきます。一つずつ考えましょう。
まず、渡される値が、 ${}_7 \mathrm{C} _3$ から ${}_n \mathrm{C} _r$ になります。

${}_7 \mathrm{C} _3$ → ${}_n \mathrm{C} _r$

そしてさっきのコードを見ていきましょう。i<5,j<6,k<7などの数字が何を表してるのか考えましょう。
まず、i,j,kというのは、それぞれ1番目、2番目、3番目に選ぶ数を表していますよね。
そしてi<5の、5は1番目の数字を選ぶ回数です。これは、7個ある内から3個選ぶ中の1番目なので、7個有る内の最後2つは選ぶことがない。よって5となっているわけですね。
つまり、1番目に選ばれる可能性のある最大値が5なわけです。
同様に2番目は6、3番目は7となるわけですね。
これを一般化すると、n個からr個取り出すとき、k番目に選ぶ数の最大値は、 $n-r+k$ となることがわかります。これでさっきのfor文を書き換えてみます。

for(i=0;i<n-r+1;i++){
  for(j=i+1;j<n-r+2;j++){
    // 略


    for(q=p+1;q<n;q++){
      printf("%d%d....%d\n",i,j,...,q);
    }
    // 略 


  }
}

これで抽象化できました。
ここまで来たら、再帰の形に持っていくことがしやすくなります。

再帰の形にする

今回の形を見ると、単純にひたすらfor文の中でfor文を呼び出せば良さそうですね。

void recursive(){
  if(// 終了条件){
    // 処理
    return;
  }

  for(i=0;i<n-r+k;i++){
    recursive();
  }
}

だいたい形はこんな感じですね。次に、引数に何を渡したらいいかを考えます。

まず、nとrですね。それと、何番目かを表す数としてkも渡しましょう。
するとこうなりますね。

void recursive(int n, int r, int k){
  if(// 終了条件){
    // 処理
    return;
  }

  for(i=0;i<n-r+k;i++){
    recursive(n,r,k+1);
  }
}

これでループが回せそうですね。

、、、ほんとに大丈夫でしょうか。
足りないところがありますね。

先程のfor文を思い出してみましょう。

for(i=0;i<n-r+1;i++){
  for(j=i+1;j<n-r+2;j++){
    // 略


    for(q=p+1;q<n;q++){
      printf("%d%d....%d\n",i,j,...,q);
    }
    // 略 


  }
}

i,j,p,qなど、ループの変数の初期値が必要ですね。適当にpとして渡しましょう。

void recursive(int n, int r, int k, int p){
  if(// 終了条件){
    // 処理
    return;
  }

  for(i=p;i<n-r+k;i++){
    recursive(n,r,k+1,i+1);
  }
}

これで今度こそループが回せますね。

終了条件を定義しましょう。今回は、最後の数を選んだとき、即ちk=rのときですね。 kが何番目の数か、rが選びたい個数を表していますからね。

void recursive(int n, int r, int k, int p){
  if(k == r){
    // 処理
    return;
  }

  for(i=p;i<n-r+k;i++){
    recursive(n,r,k+1,i+1);
  }
}

これで再帰部分は完成です！あとはやりたい処理を書いてあげましょう。

今回は組み合わせを列挙したいんでしたね。ここで、少し困ったことが発生します。
最初のfor文では、i,j,kなどのループの変数をそのまま出力すればよかったですが、再帰関数になったことで、それができません。どうしましょうか。

そんなときは、別のところに記録してあげればいいです。配列にでもメモしておきましょう。
ということで、このように書き換えます。

void recursive(int T[], int n, int r, int k, int p){
  if(k == r+1){
    // 処理
    return;
  }

  for(i=p;i<n-r+k;i++){
    T[k] = i;
    recursive(T, n,r,k+1,i+1);
  }
}

kが1から始まるので、終了条件を修正しました。
これで、出力したい値がメモされます。あとは出力してあげるだけですね。

void recursive(int T[], int n, int r, int k, int p){
  int i;
  if(k == r+1){
    for(i=0;i<r;i++){
      printf("%d ",T[i+1]);
    }
    printf("\n");
    return;
  }

  for(i=p;i<n-r+k;i++){
    T[k] = i;
    recursive(T, n,r,k+1,i+1);
  }
}

これで再帰関数が完成です！使いやすくするなら、次のような、初期値を与えてあげる関数を用意するといいでしょう。

void callRecursive(int n, int r){
  int T[100000];
  recursive(T,n,r,1,0);
}

まとめ

まず具体的に考える
抽象化する
再帰関数にまとめる

僕の中での再帰関数を作るときの思考プロセスとしてこうすればいいんじゃないかと思ったことを記事に起こしました。
再帰関数って、原理はわかっても、直感的じゃないので実際組み立てるのって難しいですよね。
そこを咀嚼したので、誰かの参考にはなるでしょうか？