Part.13

関数の再帰呼び出しとポインタの初歩

内容

  • 関数の再帰呼び出し
  • ポインタ・初級

関数の再帰呼び出し

関数の再帰呼び出しを使うと，プログラムの記述がすっきりする場合があります．例えば，最大公約数を求めるユークリッドの互除法のアルゴリズムやフラクタル画像の描画など，再帰呼び出しを使うとスマートに記述できます．

ユークリッドの互除法

これから，二つの整数の最大公約数を求めるという問題に取り組みます．最大公約数とは共通の約数のうち最大なもので，２個の整数m, n の最大公約数とは，m=ad, n = bd を満たす整数 a,b が存在するような最大の整数 d です．これを，gcd(m, n) と書く事にしましょう．(gcd は Greatest Common Divisor の略)

さて，負でない整数 x, y の最大公約数は，x を y で割ったあまりを r としたとき，

gcd(x, y) = gcd(y, r)

である事を用いて効率よく求める事ができ，ユークリッドの互除法と呼ばれています．上記を書き換えると，

gcd(x, y) = gcd(y, x mod y)

となります．つまり，まとめると，ユークリッドの互除法は次のようになります．

gcd(x, y) = gcd(y, x mod y) (y != 0 のとき）

gcd(x, y) = x (y == 0 のとき）

これを繰り返せば，最大公約数が求まります．具体例を見ましょう．以後，mod を % と書きます（Ｃ言語風）。

gcd(12707, 12319) = gcd(12319, 12707%12319) = gcd(12319, 388)
-->gcd(12319, 388) = gcd(388, 12319%388) = gcd(388, 291)
-->gcd(388, 291) = gcd(291, 388%291) = gcd(291, 97)
-->gcd(291, 97) = gcd(97, 291%97) = gcd(97, 0)
-->gcd(97, 0) = 97

よって，12707 と 12319 の最大公約数は 97 である事が求まります．

さて，このアルゴリズムをC言語で実装しましょう．

最大公約数を求める関数 gcd（その１）

これまでの知識を用いて，gcd(x, y)を求める関数 gcd を作りましょう．mod は C言語では % と書きますので次のようになります．

int gcd(int x, int y)
{
  int t;
  while(y != 0)
  {
    t = x % y;
    x = y;
    y = t;
  }
  return x;
}

最大公約数を求める関数 gcd（その２）

関数の再帰呼び出しを用いるとよりスマートにかけます．

int gcd(int x, int y)
{
  if(y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x%y);
  }
}

gcd その２ の動作を実際に見ることで，関数の再帰呼び出しを理解しましょう．ここの gcd の定義の部分には，その動作を見る為に printf 文を追加しています．これを今日のプロジェクト 01 とします．

#include <stdio.h>
int gcd(int x, int y);

int main()
{
  printf("gcd(12707, 12319) =%d\n", gcd(12707, 12319) );
  return 0;
}
   
int gcd(int x, int y)
{
  printf("-->gcd(%d, %d)\n", x, y);
    
  if(y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x%y);
  }
}

上記プログラムを実行すると以下の様な出力が得られます．

-->gcd(12707, 12319)
-->gcd(12319, 388)
-->gcd(388, 291)
-->gcd(291, 97)
-->gcd(97, 0)
gcd(12707, 12319)=97

関数 gcd の定義の中に gcd 自身が入っているので，関数の再帰呼び出しとよばれます．プログラムの動作を実際に目で追って，よく理解してください．先のユークリッドの互除法の説明部分そのままにプログラミングされていて，そのままに動作する事を確認してください．はじめは分かりにくいですが，よく見る事で理解できますし，それ以外理解できるようになる方法はありません．

また，gcd(0, 0) は定義されませんが，gcd(0, 0) と定めると，３個の負でない整数の最大公約数は gcd(a, b, c) = gcd(gcd(a, b), c) として求められる．４個以上も同様．

課題１

２個の整数 m, n の最小公倍数 lcm(m, n) は |mn|/gcd(m, n) として求められる(|mn|は m*n の絶対値)．２個の負でない整数を引数として受け取り，それらの最小公倍数を戻り値として返す関数 lcm を作成せよ(lcm は Least Common Multipleの略)．既に作成済みの gcd 関数を用いると良い．絶対値の計算には，標準関数 abs を用いる事ができる．標準関数 abs は，引数として整数を一つ受け取り，戻り値はその引数の絶対値である．但し，標準関数の一つであるabs関数を用いるには，

#include <stdlib.h>

を #include <stdio.h> の下に書き加える必要がある．

ポインタ・初級

ポインタの概念は，わかってしまえば簡単ですが，記法が特殊で混乱しやすいため，口頭で補足説明を行いますので注意して聞いて下さい．幾つか本を読んでもどうもよくわからないという人や，何となくわかったつもりで使っている人も良くいますが，ここである程度しっかり理解しておきましょう．

これまで関数の利用において，複数の入力に対して，戻り値は一つの場合のみ扱ってきました．場合によっては，複数の戻り値を得たい場合もあるでしょう．C言語の特徴でもあるポインタを使えば，そのような事が可能になります．（ポインタの概念は便利ですが，間違った使い方をすると，たちの悪いプログラムを作ってしまうことになりますから注意して使いましょう．特に配列を使う場合にはポインタの概念を良く理解する事が必要になります．）

例えば，二つの数値を与えると，それら数値の単純和・絶対値和・積の三つの計算をして答えを返す関数を作りたいとします．これまでの知識ではうまく行きません．例えば次の様なプログラムでうまく行きそうですがうまく行かない事を見て見ましょう．これをプロジェクト 02 とします．

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

void calc01(int a, int b, int plus, int absplus, int mult);

int main()
{
  int a, b, c;
  a = 0; b = 0; c = 0;
  calc01(10, -10, a, b, c);
  printf("%d %d %d\n", a, b, c);
  return 0;
}

void calc01(int a, int b, int plus, int absplus, int mult)
{
  plus = a + b;
  absplus = abs(a) + abs(b);
  mult = a*b;
}

幾つか注意点があります．まず，絶対値を求める標準関数 abs を使うため， #include <stdlib.h> が記述されています．また，calc01 関数について void とありますが，これは（関数としての）戻り値無しという意味です．（関数 calc01 の定義内に return 文が無い）

main 関数内で整数型変数 a, b, c を用意し，それを calc01 に渡し，その中で計算内容を代入を代入しているので，結果が表示されそうな物ですがうまく行きません．

C言語において，上記の様な関数の記述では，関数の対応する変数に対して「値」が渡されます．つまり， main 関数内での calc01 の呼び出しでは，

calc01(10, -10, a, b, c);

となっていますが，a, b, c それぞれの変数の中に格納されている値が calc01 の定義にあるそれぞれ plus, absplus, mult に代入されます．main 関数内の a, b, c と calc01 内の plus, absplus, mult は別のもの（別の箱）ですから，calc01 内の plus, absplus, multに計算結果を代入しても main 関数内の a, b, cに値は入りません．ちなみに，変数名を同じにしてもうまく行きません．例えば，次の様．

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

void calc01(int a, int b, int plus, int absplus, int mult);

int main()
{
  int plus, absplus, mult;
  plus = 0; absplus = 0; mult = 0;
  calc01(10, -10, plus, absplus, mult);
  printf("%d %d %d\n", plus, absplus, mult);
  return 0;
}

void calc01(int a, int b, int plus, int absplus, int mult)
{
  plus = a + b;
  absplus = abs(a) + abs(b);
  mult = a*b;
}

では，どのようにすればよいか？関数に箱を渡して，その箱に値を入れてもらえば良いという事になります．より正確には，箱の位置を教えることで，その場所に計算結果を入れてもらう事ができます．それがポインタです．次のプログラムは期待通りに動きます．

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

void calc01(int a, int b, int *plus, int *absplus, int *mult);

int main()
{
  int a, b, c;
  a = 0; b = 0; c = 0;
  calc01(10, -10, &a, &b, &c);
  printf("%d %d %d\n", a, b, c);
   
  return 0;
}

void calc01(int a, int b, int *plus, int *absplus, int *mult)
{
  *plus = a + b;
  *absplus = abs(a) + abs(b);
  *mult = a*b;
}

これまで出てこなかった * や & が出てきました．（& は scanf で出てきましたが，ここでの理由と同じです．）

int *plus;

で plus という名前の整数型変数へのポインタを定義します．「整数型変数へのポインタ」とは整数型変数の位置（アドレス）を格納する変数です．

int a;

で定義された整数型変数について，その値が保管されるメモリ上の位置をアドレスと呼びますが，それは &a で表されます．つまり，このプログラムでは，関数 calc01 に main 関数内の変数 a, b, c のアドレスを渡す事で，その場所に結果を書き込むことを行っています．また，

int *plus;

で定義されたポインタ変数に「値」を代入するには

*plus = 10;

という風に最初に * をつけます．

次の例を見てみましょう．

#include <stdio.h>

int main()
{
  int a = 11;
  int *b;
   
  b = &a;
   
  *b = 22;
   
  printf("%d\n", a);
   
  return 0;
}

22と表示されます．この例では

b = &a;

によってa に対して代入することと， *b に対して代入することが同じ意味となっています．

課題２

ポインタを利用して，入力が２つに対して２つ以上の出力が得られる関数を新たに作りなさい．またその関数を利用する main 関数も書く事．