M.Hiroi's Home Page

Linux Programming

お気楽C言語プログラミング超入門

[ PrevPage | Clang | NextPage ]

関数

前回と前々回でC言語の基本的なデータ型と制御構造について一通り説明しました。今回は「関数 (function)」の基本的な使い方と「再帰定義」について説明します。

●関数の基礎知識

プログラミングは模型を組み立てる作業と似ています。簡単な処理はC言語の機能やライブラリを使って実現することができます。ところが、模型が大きくなると、一度に全体を組み立てるのは難しくなります。このような場合、全体をいくつかに分割して、まずその部分ごとに作ります。最後に、それを結合して全体を完成させます。

これはプログラミングにも当てはまります。実現しようとする処理が複雑になると、一度に全部作ることは難しくなります。そこで、全体を小さな処理に分割して、一つ一つの処理を作成し、それらを組み合わせて全体のプログラムを完成させます [*1]

分割した処理を作成する場合、それを一つの部品として扱えると便利です。つまり、小さな部品を作り、それを使って大きな部品を作り、最後にそれらを組み合わせて全体を完成させます。このとき、もっとも基本となる部品が「関数」です。

-- note --------
[*1] このような方法を「分割統治法」といいます。

●関数の定義方法

C言語の関数定義はとても簡単です。例題として、数を二乗する関数を作ってみましょう。次のリストを見てください。

リスト : 数を二乗する関数 (sample30.c)

#include <stdio.h>

int square(int x)
{
  return x * x;
}

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

関数定義の構文を下図に示します。

データ型 名前(仮引数名, ...)
{
  処理A;
  処理B;
  ...
}

図 : C言語の関数定義

関数の定義は下図のように数式と比較するとわかりやすいでしょう。

square が関数名、( ) の中の x が入力データを受け取る引数、ブロック { } の中の return x * x が実行される処理です。関数定義で使用する引数のことを「仮引数」、実際に与えられる引数を「実引数」といいます。square の定義で使用した x が仮引数で、square(10) の 10 が実引数になります。仮引数は変数と同じ方法で宣言します。データ型のあとに名前を指定します。ただし、初期値を指定することはできません。

そして、関数が出力する値を「返り値」といいます。返り値のデータ型は関数名の前で指定します。C言語の場合、関数の値は return 文を使って返します。return x * x; とすることで、x * x の計算結果を返します。

それでは実際に実行してみましょう。

$ clang sample30.c
$ ./a.out
100

なお、値を返さない関数も定義することができます。この場合、返り値のデータ型には void を指定してください。

●局所変数と外部変数

それでは、ここで変数 x に値が代入されている場合を考えてみましょう。次の例を見てください。

リスト : 局所変数と外部変数 (sample31.c)

#include <stdio.h>

int x = 10;

int square(int x)
{
  return x * x;
}

int main(void){
  printf("%d\n", x);
  printf("%d\n", square(5));
  printf("%d\n", x);
  return 0;
}
$ clang sample31.c
$ ./a.out
10
25
10

関数の外側で変数 x を定義しています。C言語ではこれを「外部変数」といいます。関数 main の中で、最初の printf は外部変数 x を参照するので 10 が表示されます。それでは、square(5) の実行結果はどうなると思いますか。x には 10 がセットされているので 10 の二乗を計算して返り値は 100 になるのでしょうか。これは 5 の二乗を計算して結果は 25 になります。そして、square を実行したあとでも外部変数 x の値は変わりません。

square の仮引数 x は、その関数が実行されている間だけ有効です。このような変数を「ローカル変数 (local variable)」もしくは「局所変数」といいます。これに対し、プログラムのどこからでもアクセスできる変数を「グローバル変数 (golbal variable)」もしくは「大域変数」といいます。C言語の外部変数は大域変数で、同一ファイル内であればどこからでも参照することができます。C言語は変数の値を求めるとき、それが局所変数であればその値を参照します。局所変数でなければ外部変数の値を参照します。

プログラムを作る場合、関数を部品のように使います。ある関数を呼び出す場合、今まで使っていた変数の値が勝手に書き換えられると、呼び出す方が困ってしまいます。部品であるならば、ほかの処理に影響を及ぼさないように、自分自身の中で処理を完結させることが望ましいのです。これを実現するための必須機能が局所変数なのです。

●局所変数の定義と有効範囲

C言語の場合、関数の仮引数は局所変数になりますが、それ以外にも関数の中で局所変数が必要になる場合があります。C言語は関数内で宣言された変数を局所変数として扱います。今まで関数 main の中で変数を宣言しましたが、これらの変数はすべて局所変数になります。

簡単な例を示しましょう。

リスト : 局所変数の有効範囲 (sample32.c)

#include <stdio.h>

int main(void)
{
  int x = 1;
  {
    int y = 2;
    {
      int z = 3;
      printf("%d\n", x);
      printf("%d\n", y);
      printf("%d\n", z);
    }
    printf("%d\n", x);
    printf("%d\n", y);
    // printf("%d\n", z);  z は範囲外 (コンパイルエラー)
  }
  printf("%d\n", x);
  // printf("%d\n", y);    y は範囲外 (コンパイルエラー)
  // printf("%d\n", z);    z は範囲外 (コンパイルエラー)
  return 0;
}
$ clang sample32.c
$ ./a.out
1
2
3
1
2
1

局所変数が値を保持する期間のことを、変数の「有効範囲 (scope : スコープ)」といいます。C言語の場合、局所変数の有効範囲は変数が定義されているブロックの中だけです。for 文の場合も同じで、初期化処理で宣言された局所変数は、そのあとのブロックが有効範囲になります。

変数 x は関数 main の一番外側のブロックで定義されているので、main の処理が終了するまで有効です。変数 y は 2 番目のブロックで、変数 z は 3 番目のブロックで定義されているので、各々のブロックの終わりまでが変数の有効範囲になります。ブロックの実行が終了すると、そのブロックで定義された局所変数は廃棄されます。

したがって、3 番目のブロックの中では変数 x, y, z が有効です。ブロックの処理が終了すると変数 z が廃棄されるので、2 番目のブロックの中では変数 x, y が有効です。そして、そのブロックの処理が終了すると、変数 y が廃棄されるので有効な変数は x だけになります。

関数の仮引数は局所変数と同じと考えてください。関数を呼び出すとき、実引数を仮引数に代入してから、関数本体の処理を実行します。関数の実行が終了するとき、仮引数は廃棄されます。

●素数を求める (2)

それでは関数を使って、前回作成した素数を求めるプログラムを書き直して見ましょう。次のリストを見てください。

リスト : 素数を求める (sample33.c)

#include <stdio.h>
#include <stdbool.h>

#define N 100

// 素数を格納する配列
int prime_table[N];
int prime_size;

// 初期化
void init_prime(void)
{
  prime_table[0] = 2;
  prime_size = 1;
}

// 素数か?
bool is_prime(int n)
{
  for (int i = 0; i < prime_size; i++) {
    int p = prime_table[i];
    if(p * p > n) break;
    if(n % p == 0) return false;
  }
  return true;
}

// 素数を追加する
void push_prime(int n)
{
  prime_table[prime_size++] = n;
}

// 素数の表示
void print_prime(void)
{
  for (int i = 0; i < prime_size; i++)
    printf("%d ", prime_table[i]);
  printf("\n");
}

int main(void)
{
  // 初期化
  init_prime();
  // 素数を求める
  for (int n = 3; n <= N; n += 2)
    if (is_prime(n)) push_prime(n);
  // 表示
  print_prime();
  return 0;
}
$ clang sample33.c
$ ./a.out
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

数値 n が素数か判定する処理を関数 is_prime で行うように変更します。is_prime は数値 n を受け取り、n が素数で割り切れれば false を返し、そうでなければ true を返します。for ループの中で return false を実行すれば、is_prime の処理を終了して false を返すことができます。

is_prime を使うと、素数を求める処理は簡単にプログラムすることができます。is_prime が true を返したら n を配列 prime_table に追加するだけです。この処理も関数 push_prime で行うように修正しています。同様に、prime_table の初期化と素数の表示も関数にしています。このように、処理を分割して関数に割り当てることにより、関数 main はとてもわかりやすいプログラムになります。

●めのこ平方

もうひとつ簡単な例題として、平方根の整数部分を求める関数 sqrt_int を作ってみましょう。平方根の整数部分は次の公式を使って求めることができます。

\(\begin{array}{ll} (1) & 1 + 3 + 5 + \cdots + (2n - 1) = n^2 \\ (2) & 1 + 3 + 5 + \cdots + (2n - 1) = n^2 \lt m \lt 1 + 3 + \cdots + (2n - 1) + (2n + 1) = (n + 1)^2 \end{array}\)

式 (1) は、奇数 \(1\) から \(2n - 1\) の総和は \(n^2\) になることを表しています。式 (2) のように、整数 m の値が \(n^2\) より大きくて \((n + 1)^2\) より小さいのであれば、m の平方根の整数部分は n であることがわかります。これは m から奇数 \(1, 3, 5, \ldots, (2n - 1), (2n + 1)\) を順番に引き算していき、引き算できなくなった時点の (2n + 1) / 2 = n が m の平方根になります。参考文献 1 によると、この方法を「めのこ平方」と呼ぶそうです。

プログラムは次のようになります。

リスト : めのこ平方 (sqrtint.c)

#include <stdio.h>

int sqrt_int(int n)
{
  int m = 1;
  while (n >= m) {
    n -= m;
    m += 2;
  }
  return m / 2;
}

int main(void)
{
  printf("%d\n", sqrt_int(100));
  printf("%d\n", sqrt_int(1000));
  printf("%d\n", sqrt_int(10000));
  printf("%d\n", sqrt_int(123456789));
  return 0;
}
$ clang sqrtint.c
$ ./a.out
10
31
100
11111

アルゴリズムをそのままプログラムしただけなので、とくに難しいところは無いと思います。この方法はとても簡単ですが、数が大きくなると時間がかかるようになります。これはあとで改良してみましょう。

●再帰定義

関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。再帰定義といえば関数型言語の専売特許だと思われている方もいるでしょう。実際、初心者の方は再帰定義を難しいテクニックのひとつと思い込んでしまい、避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。

\(\begin{array}{l} 0! = 1 \\ n! = n \times (n - 1)! \end{array}\)

図 : 階乗の定義

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。

リスト : 階乗 (fact.c)

#include <stdio.h>

int fact(int n)
{
  if (n == 0)
    return 1;
  else
    return n * fact(n - 1);
}

int main(void)
{
  for (int i = 0; i < 13; i++)
    printf("%d! = %d\n", i, fact(i));
  return 0;
}
$ clang fact.c
$ ./a.out
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600

関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。

階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。

このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。次の図を見てください。


          図 : fact の再帰呼び出し (n:引数の値, value:返り値)

上図は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。

関数の引数は局所変数として扱われます。局所変数には有効範囲(スコープ)があります。引数の場合、その関数が実行されている間だけ有効です。局所変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの「停止条件」といいます。ここが第 2 のポイントです。停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Unix 系 OS では Segmentation fault (コアダンプ) が発生して、プログラムの実行は中止されます。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。

●ユークリッドの互除法

もう一つ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。

[ユークリッドの互除法]
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。

ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。

\(a = q \times b + r \quad \quad (1)\)

ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。

\(m \times a' = q \times m \times b' + r \quad \quad (2)\)

左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。

\(m \leq m' \quad \quad (3)\)

次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。

\(a = q \times m' \times b'' + m' \times r' \quad \quad (4)\)

右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。

\(m' \leq m \quad \quad (5)\)

式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。

あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。

プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。

リスト : 最大公約数 (gcd.c)

#include <stdio.h>

// 最大公約数
int gcd(int a, int b)
{
  return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b)
{
  return a * b / gcd(a, b);
}

int main(void)
{  
  printf("%d\n", gcd(42, 30));
  printf("%d\n", gcd(15, 70));
  printf("%d\n", lcm(5, 7));
  printf("%d\n", lcm(14, 35));
  return 0;
}

関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd を再帰呼び出しして、b と a % b の最大公約数を求めます。リストはユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。

また、整数 a と b の最小公倍数 (lcm) は a * b / gcd(a, b) で求めることができます。それでは実行例を示します。

$ clang gcd.c
$ ./a.out
6
5
35
70

●相互再帰と関数プロトタイプ

相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。C言語はコンパイル型のプログラミング言語なので、foo から bar を呼び出すとき、bar が未定義の場合はコンパイルでワーニングが発生します。次のリストを見てください。

リスト : 相互再帰 (sample34.c)

#include <stdio.h>
#include <stdbool.h>

// プロトタイプ宣言が必要
// bool bar(int n);

bool foo(int n)
{
  return n == 0 ? true : bar(n - 1);
}

bool bar(int n)
{
  return n == 0 ? false : foo(n - 1);
}

int main(void)
{
  printf("%d\n", foo(10));
  printf("%d\n", foo(11));
  printf("%d\n", bar(20));
  printf("%d\n", bar(21));
  return 0;
}
sample34.c:9:26: warning: implicit declaration of function 'bar' is invalid in C99
[-Wimplicit-function-declaration]
  return n == 0 ? true : bar(n - 1);
                         ^
sample34.c:12:6: error: conflicting types for 'bar'
bool bar(int n)
     ^
sample34.c:9:26: note: previous implicit declaration is here
  return n == 0 ? true : bar(n - 1);
                         ^
1 warning and 1 error generated.

C言語は定義されていない関数があると、int を返す関数とみなしてコンパイルします。これを関数の「暗黙的な宣言 (implicit declaration)」といいます。返り値が int としてコンパイルしようとするのですが、あとから bool を返す関数 bar の定義が見つかったのでコンパイルエラーになります。

このプログラムで bar と foo の返り値を int にすると、ワーニングは表示されますがコンパイルは通ります。実際にプログラムも正常に動作します。ただし、暗黙的な宣言では引数のチェックができないので、関数 foo で bar を呼び出すとき、bar() としてもワーニングが表示されるだけで、コンパイルは通ってしまいます。この場合、プログラムは正常に動作しません。

C言語は事前に関数の引数の型や返り値の型を宣言することができます。これを「関数プロトタイプ (function prototype)」といいます。プロトタイプは関数定義から本体を省略した形式になります。プロトタイプの構文を示します。

データ型 関数名(データ型 仮引数, ...);

プロトタイプでは仮引数を省略して、データ型だけ記述してもかまいません。sample34.c では関数 foo の前に、プロトタイプ宣言 bool bar(int n); を追加するとワーニングは発生しません。また、bar を引数無しで呼び出すとコンパイルエラーになります。

標準ライブラリ関数を呼び出す場合、C言語ではヘッダファイルをインクルードしますが、このヘッダファイルの中にライブラリ関数のプロトタイプが定義されています。ヘッダファイルをインクルードしないと、暗黙的な宣言により int を返す関数とみなされてしまいます。また、引数のチェックも行われないので、コンパイルは通ってもプログラムは正常に動作しないこともありえます。ライブラリ関数を呼び出すときは、ヘッダファイルをインクルードすることをお忘れなく。

このプログラムは関数 foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。

$ clang sample34.c
$ ./a.out
1
0
0
1

結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。

●末尾再帰と繰り返し

再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*2] といいます。なかには Scheme [*3] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。

たとえば、階乗を計算する関数 fact を思い出してください。fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。

リスト : 階乗 (末尾再帰, facti.c)

#include <stdio.h>

int facti(int n, int a)
{
  return n == 0 ? a : facti(n - 1, a * n);
}

int main(void)
{
  for (int i = 0; i < 13; i++)
    printf("%d! = %d\n", i, facti(i, 1));
  return 0;
}
$ clang facti.c
$ ./a.out
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600

最後の再帰呼び出しで、関数 facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。

たとえば facti(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出しを下図に示します。

facti(4, 1)
|   facti(3, 4)
|   |   facti(2, 12)
|   |   |   facti(1, 24)
|   |   |   |   facti(0, 24)
|   |   |   |   => a の値 24 を返す
|   |   |   => 24
|   |   => 24
|   => 24
=> 24

        図 : facti の動作

引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。

関数型言語の場合、while文 や for文 などの繰り返し文がないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

ところで、最大公約数を求める関数 gcd は末尾再帰になっています。C言語の場合、末尾再帰最適化は規格の範囲外で、Cコンパイラの最適化に依存する機能になりますが、私たちが繰り返しに変換するのは簡単です。次のリストを見てください。

リスト : 最大公約数を求める (gcdi.c)

#include <stdio.h>

// 最大公約数 (繰り返し版)
int gcdi(int a, int b)
{
  while (b > 0) {
    int c = a;
    a = b;
    b = c % b;
  }
  return a;
}

int main(void)
{  
  printf("%d\n", gcdi(42, 30));
  printf("%d\n", gcdi(15, 70));
  return 0;
}
$ clang gcdi.c
$ ./a.out
6
5

関数 gcdi は引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。

繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムが一番です。

-- note --------
[*2] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。興味のある方は Appendix; 末尾最適化 をお読みください。
[*3] Scheme は Lisp の方言の一つで、熱心なユーザが多いプログラミング言語です。

●めのこ平方の改良

それでは再帰定義を使ってめのこ平方のプログラムを改良してみましょう。ポイントは、整数を 2 桁ずつ分けて計算していくことです。次の図を見てください。

整数 6789 を 67 と 89 に分ける

1 + 3 + ... + 15 = 82 < 67

両辺を 100 倍すると 802 < 6700 < 6789

802 = 1 + 3 + ... + 159 (= 2 * 80 - 1)

161 + 163 < (6789 - 6400 = 389) < 161 + 163 + 165

整数 6789 を 67 と 89 に分けます。最初に 67 の平方根を求めます。この場合は 8 になり、82 < 67 を満たします。次に、この式を 100 倍します。すると、802 < 6700 になり、6700 に 89 を足した 6789 も 802 より大きくなります。802 は 1 から 159 までの奇数の総和であることはすぐにわかるので、6789 - 6400 = 389 から奇数 161, 163, ... を順番に引き算していけば 6789 の平方根を求めることができます。

プログラムは次のようになります。

リスト : めのこ平方 (sqrtint1.c)

#include <stdio.h>

int sqrt_int(int n, int m)
{
  while (n >= m) {
    n -= m;
    m += 2;
  }
  return m / 2;
}

int sqrt_int1(int n)
{
  if (n < 100)
    return sqrt_int(n, 1);
  else {
    int m = 10 * sqrt_int1(n / 100);
    return sqrt_int(n - m * m, 2 * m + 1);
  }
}

int main(void)
{
  printf("%d\n", sqrt_int1(1000000));
  printf("%d\n", sqrt_int1(123456789));
  printf("%d\n", sqrt_int1(1234567890));
  return 0;
}
$ clang sqrint1.c
$ ./a.out
1000
11111
35136

sqrt_int1 は n の平方根の整数部分を求めます。n が 100 未満の場合は sqrt_int で平方根を求めます。これが再帰呼び出しの停止条件になります。n が 100 以上の場合は、n の下位 2 桁を取り除いた値 (n / 100) の平方根を sqrt_int1 で求め、その値を 10 倍して変数 m にセットします。そして、sqr_int で n - m * m から奇数 2 * m + 1, 2 * m + 3 ... を順番に引き算していって n の平方根を求めます。

●順列の生成

最後に「順列 (permutation)」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) 通りあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。次のリストを見てください。

リスト : 順列の生成 (繰り返し版)

#include <stdio.h>
#include <stdbool.h>

#define N 4

int  buff[N];     // 順列を格納する配列
bool used[N + 1]; // 使用した数字

int main(void)
{
  // 一つ目の数字を選ぶ
  for (int n1 = 1; n1 <= N; n1++) {
    if (used[n1]) continue;
    buff[0] = n1;
    used[n1] = true;
    // 二つ目の数字を選ぶ
    for (int n2 = 1; n2 <= N; n2++) {
      if (used[n2]) continue;
      buff[1] = n2;
      used[n2] = true;
      // 三つ目の数字を選ぶ
      for (int n3 = 1; n3 <= N; n3++) {
       if(used[n3]) continue;
       buff[2] = n3;
       used[n3] = true;
       // 四つ目の数字を選ぶ
       for (int n4 = 1; n4 <= N; n4++) {
         if (used[n4]) continue;
         buff[3] = n4;
         used[n4] = true;
         // 順列を出力
         for(int i = 0; i < N; i++) printf("%d ", buff[i]);
         printf("\n");
         used[n4] = false;
       }
       used[n3] = false;
      }
      used[n2] = false;
    }
    used[n1] = false;
  }
  return 0;
}

少々長いリストですが、やっていることは簡単です。選んだ数字は配列 buff に格納し、配列 used に印 (true) をつけておきます。あとは used に印がついていない数字を選んでいくだけです。数字を 4 つ選んだら順列 buff を出力します。

そして、次の順列を発生させるため、選んだ数字に対応する used に false をセットします。選ぶ数字がなくなったならば、もう一つ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成することができます。

このプログラムは 4 重のループですが、けっこうたいへんですね。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムを作ることができます。次のリストを見てください。

リスト : 順列の生成 (再帰版)

#include <stdio.h>
#include <stdbool.h>

#define N 8

int  buff[N];      // 順列を格納する配列
bool used[N + 1];  // 使用した数字

// 順列の表示
void print_perm(int m)
{
  for (int i = 0; i < m; i++) printf("%d ", buff[i]);
  printf("\n");
}

int perm(int m, int n)
{
  if (n == m)
    print_perm(m);
  else
    for (int i = 1; i <= m; i++) {
      if (used[i]) continue;
      buff[n] = i;
      used[i] = true;
      perm(m, n + 1);
      used[i] = false;
    }
  return 0;
}

int main(void)
{
  perm(3, 0);
  perm(4, 0);
  return 0;
}

関数 perm は、1 から m までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで buff にセットし、used に印 (true) をつけます。あとは印のついていない数字を選んでいけばいいのです。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。

たとえば、n 番目の数字を選び順列を出力したら、n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。その後は選んだ数字の印を消して、新しい数字を選びます。もしも、選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から m までの順列をすべて生成することができます。

それでは実行してみましょう。

$ clang perm1.c
$ ./a.out
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

このように 3! = 6 通りと 4! = 24 通りの順列をすべて求めることができます。

●参考文献

  1. 仙波一郎のページ, 『平方根計算法 (PDF)』

●Appendix: 末尾最適化

末尾再帰についてもう少し詳しく説明しましょう。末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call)」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。

このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization)」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。

また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization)」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰最適化を行う処理系があります。なかには Scheme のように、言語仕様に末尾最適化を行うことを明記しているプログラミング言語もあります。最近では、C言語 (gcc や clang など) でも末尾最適化が可能になっています。

簡単な例を示しましょう。1 から n までの総和を末尾再帰で求めます。

リスト : 1 から n までの総和 (末尾再帰)

#include <stdio.h>

double sum(int n, double a)
{
  if (n == 0) {
    return a;
  } else {
    return sum(n - 1, a + n);
  }
}

int main()
{
  int i = 10000;
  int j = 0;
  for (; j < 6; i *= 2, j++) {
    printf("%d, %.0f\n", i, sum(i, 0));
  }
  return 0;
}

関数 sum は末尾再帰になっています。clang の場合、最適化オプション -O を指定すると末尾最適化が行われます。-O を指定しないと最適化は行われません。なお、gcc で末尾最適化を有効にするには -O2 を指定してください。

実行結果を示します。

$ clang sum.c
$ ./a.out
10000, 50005000
20000, 200010000
40000, 800020000
80000, 3200040000
160000, 12800080000
Segmentation fault

$ clang -O sum.c
$ ./a.out
10000, 50005000
20000, 200010000
40000, 800020000
80000, 3200040000
160000, 12800080000
320000, 51200160000

このように、-O を指定しないとスタックオーバーフローによりコアダンプが発生しますが、-O を指定すると末尾最適化によりスタックオーバーフローせずに総和を計算することができます。

また、次のような相互再帰でも最適化することができます。

リスト : 相互再帰

#include <stdio.h>

/* 関数宣言 */
int odd(int);
int even(int);

int even(int n)
{
  if (n == 0) {
    return 1;
  } else {
    return odd(n - 1);
  }
}

int odd(int n)
{
  if (n == 0) {
    return 0;
  } else {
    return even(n - 1);
  }
}

int main()
{
  int i, j;
  for (j = 0, i = 20000; j < 5; j++, i *= 2) {  
    printf("%d, %d\n", i, even(i));
    printf("%d, %d\n", i, odd(i));
  }
}

実行結果は次のようになります。

$ clang testr.c
$ ./a.out 
20000, 1
20000, 0
40000, 1
40000, 0
80000, 1
80000, 0
160000, 1
160000, 0
Segmentation fault

$ clang -O testr.c
$ ./a.out 
20000, 1
20000, 0
40000, 1
40000, 0
80000, 1
80000, 0
160000, 1
160000, 0
320000, 1
320000, 0

-O を指定すると末尾最適化によりスタックオーバーフローせずに計算することができます。最近のCコンパイラはとても優秀ですね。興味のある方はいろいろ試してみてください。


初版 2015 年 2 月 7 日
改訂 2023 年 4 月 2 日

Copyright (C) 2015-2023 Makoto Hiroi
All rights reserved.

[ PrevPage | Clang | NextPage ]