僕は再帰が書けない

最近、かなーり古いアルゴリズム本でアルゴリズムの復習をしたりしている。

やっぱ再帰は苦手だな〜。という愚痴。

以下はC言語で、要素数4つのint配列、{0, 0, 0, 0}の要素の合計値が1以上4以下になる場合の配列の組み合わせを示したもの。

中々理解出来なかったのでメモしておく。

#include <stdio.h>
#include <stdlib.h>

int number_using[] = {0,0,0,0};

void make_numbers(int begin, int sum){
  int i, j;
  if( sum > 4){
    return;
  }
  for(i=begin; i<4; i++){

    number_using[i]++;
    printf("{ ");
    for(j=0; j<4; j++){
        printf("%d ", number_using[j]);
    }
    printf("}\n");
    make_numbers( i, sum+1 );
    number_using[i]--;
  }
}

int main(void){
  make_numbers(0, 1);
  return EXIT_SUCCESS;
}

つまり、こーんな感じの配列を羅列するのを再帰を使って書く。

{ 1 0 0 0 }
{ 2 0 0 0 }
{ 3 0 0 0 }
{ 4 0 0 0 }
{ 3 1 0 0 }
{ 3 0 1 0 }
{ 3 0 0 1 }
{ 2 1 0 0 }
{ 2 2 0 0 }
{ 2 1 1 0 }
{ 2 1 0 1 }
...
{ 0 0 0 3 }
{ 0 0 0 4 }

まず、配列内の合計値sumが4超えた場合、呼び出し元に処理を返す。

if( sum > 4){
  return;
}

このループiは配列のindexを表す。よってindex:0の要素から処理していくことになる。

for(i=begin; i<4; i++){
}

要素:0に対してsum=2とした関数を呼び出す。

void make_numbers(int begin, int sum){
  int i, j;
  if( sum > 4){
    return;
  }
  for(i=begin; i<4; i++){
    make_numbers( i, sum+1 );
  }
}

つまり、こうすることによって、i=0を維持したまま、sumに値を加えていく。

{ 1 0 0 0 }
{ 2 0 0 0 }
{ 3 0 0 0 }
{ 4 0 0 0 }

sumが境界値を超えると、一つ前の呼び出し元、sumの値が3の時の処理に戻り、ループが一つ進むみi=1となる。

{ 3 1 0 0 }

これが終わるとi=2, i=3と続き、ループが一周すると、i=0, sum=2の時の処理に戻ってくる。

{ 3 0 1 0 }
{ 3 0 0 1 }

それで再びsumの値を1加えていきーが続いていき、一番頭の呼び出しもとループのiが4に到達した時に処理が終了する。

{ 2 1 0 0 }
{ 2 2 0 0 }
{ 2 1 1 0 }
{ 2 1 0 1 }
...
{ 0 0 0 3 }
{ 0 0 0 4 }

あとは、その時処理している関数内のiに対して、値を足してあげ、再帰関数から処理が戻ってくると値を減らしてあげればよい。

int number_using[] = {0,0,0,0};

void make_numbers(int begin, int sum){
  int i, j;
  if( sum > 4){
    return;
  }
  for(i=begin; i<4; i++){

    number_using[i]++;
    make_numbers( i, sum+1 );
    number_using[i]--;
  }
}

再帰は深さ優先であることを念頭に置いて、関数の入れ子をツリーとして図示すると分かり易いかも。なんて思ってたりもした。

ただ、理屈は理解しても、すぐにこんなの書けないよ〜という自分の脳みそ...

リンク

リンク