10 printf("(2)a=%3d b=%3.0f\n", a, b);
11 {
12 int b=777;
13 printf("(3)a=%3d b=%3d\n", a, b);
14 }
15 printf("(4)a=%3d b=%3.0f\n", a, b);
16 {
17 int b=999;
18 printf("(5)a=%3d b=%3d\n", a, b);
19 }
20 printf("(6)a=%3d b=%3.0f\n", a, b);
21 }
22 printf("(7)a=%3d b=%3d\n", a, b);
23 return 0;
24 }
[motoki@x205a]$ gcc scope-of-name-lab.c Enter [motoki@x205a]$ ./a.out Enter
[motoki@x205a]$
10.3. 再帰計算 147
の関数定義の中で互いに相手の関数を呼び出し合っている場合も、間接的に自分自身を呼 び出しているので、再帰呼び出しの一種と考える。
例題 10.10 (二項係数;階乗の再帰計算) 漸化式 fi =
( 1 if i= 1 i×fi−1 if i≥2
によって fi = i! と定まる。これを考慮に入れて、整数を1個引数として受け取りそ の階乗値をdouble型で計算して返す関数 factorial() を再帰的に定義せよ。 そし て、この関数を用いて例題10.1と同じことを行うCプログラムを作成せよ。すなわ ち、2つの正整数データ nとk を読み込み、n個のものからk個を選ぶ組合せの数を
n k
= k! (nn!−k)! と計算して出力するCプログラムを作成せよ。
(考え方) 例題10.1で構成したmain()関数は、定義変更が求められている関数factorial() の呼び出しを含んでいる。しかし、ここで定義する関数factorial()の仕様(呼び出す側 に対して提供する機能) 自体は例題10.1の場合と変わらないので、main()関数について は例題10.1のものを何も変更せずにそのまま使える。従って、例題10.1で示したプログ ラムの中で、関数 factorial() を指示に従って再帰的に定義し直すだけである。
(プログラミング) 関数 factorial() を定義するにあたっては、例題10.1の場合と同じ く仮引数として k という名前のint型変数を用意した。作成したCプログラムと、これ をコンパイル/実行している様子を次に示す。(下線部はキーボードからの入力を表す。)
[motoki@x205a]$ nl binomial-coeff-using-rec-fatorial.c Enter
1 /* 2つの正整数データ n と k を読み込み */
2 /* 二項係数 n!/(k!*(n-k)!) を出力するCプログラム */
3 /* (階乗値を再帰的に計算する関数を用意する。) */
4 #include <stdio.h>
5 double factorial(int k);
6 int main(void) 7 {
8 int n, k;
9 printf("It will compute a binomial coefficient.\n"
10 "Input two positive integers n and k(<=n): ");
11 scanf("%d%d", &n, &k);
12 printf("\nThe number of the combinations of\n"
13 " n objects taken k at a time = %20.14g\n", 14 factorial(n)/(factorial(k)*factorial(n-k)));
15 return 0;
16 }
17 /*---*/
18 /* 階乗値を計算してその結果を返す関数 (再帰版) */
19 /*---*/
20 /* (入力引数) k : 何の階乗を計算するかを表す整数 */
21 /* (関数値) : k! の値をdoubleで */
22 /*---*/
23 double factorial(int k) 24 {
25 if (k <= 1) 26 return 1.0;
27 else
28 return (k * factorial(k-1));
29 }
[motoki@x205a]$ gcc binomial-coeff-using-rec-fatorial.c Enter [motoki@x205a]$ ./a.out Enter
It will compute a binomial coefficient.
Input two positive integers n and k(<=n): 50 25 Enter The number of the combinations of
n objects taken k at a time = 1.2641060643775e+14 [motoki@x205a]$
ここで、
• プログラムの23〜29行目 で階乗計算の関数 factorial() を定義しているが、この 中の28行目 で今計算手順を書こうとしている factorial() 自身を再帰的に呼んで いる。
• 11行目でkの値として 2が入力された場合 のfactorial(k) の処理の様子を次に示 す。
int main(void) {
...
factorial(n)/(factorial(k)*factorial(n-k)));
}
double factorial(int k) {
if (k<=1) return ...
else
return (k*factorial(k-1));
}
double factorial(int k) {
if (k<=1) return 1.0;
else return ...
}
k 2
k 2
k 1 (1) 呼出し
(3) 計算結果 1.0 (4) 計算結果 2*1.0=2.0
(2) 呼出し
10.4. パラメータの受渡し方法 —値呼出し vs. 参照呼出し— 149
• 漸化式の計算を行いたい場合、再帰を用いれば漸化式の形をそのまま反映した形で容 易に関数定義を行うことが出来ることに注目せよ。
□演習 10.11 ((3n+1)数列) 初期値 a1 と漸化式
an+1 =
1 if an= 1 an/2 if anが偶数 3an+ 1 otherwise
によって定まる数列 {an} を考える。 2つの正整数 aとk をパラメータとして受け取り、
初期値が a1 = a の時のこの数列の第k項の値を計算して返す関数を再帰的に定義して みよ。
□演習 10.12 (Fibonacci数列) 46以下の非負整数 k をパラメータとして受け取り、初 期値が a0 =a1 = 1 のFibonacci数列(演習10.6)の第(k+ 1)項 ak を計算結果として返 す関数を再帰的に定義してみよ。
□演習 10.13 (McCarthyの91関数) 次の漸化式によって定義される整数から整数への 関数 f(x)を計算する関数(プログラム)を再帰的に定義してみよ。また、この関数(プログ ラム)を再帰無しで定義してみよ。[補足：実はx >100の時にはf(x) =x−10, x≤100の 時にはf(x) = 91 となる。]
f(x) =
( x−10 if x >100 f(f(x+ 11)) otherwise
10.4 パラメータの受渡し方法 — 値呼出し vs. 参照呼出し —
実引数と仮引数の対応付け： 関数呼び出しの際には、呼ぶ側と呼ばれる側の情報交換、
すなわち関数呼び出し側の引数(実引数または実パラメータという)と関数定義側の引数
(仮引数または仮パラメータという)の結合／対応付けが行われる。 引数結合の方式とし
ては次の2つが一般によく用いられている。
• 値呼出し(call by value)· · ·実引数として与えられた式が評価／計算され、その値が 仮引数の変数の初期値として使われる。
• 参照呼出し(call by reference) · · · 実引数として与えられた変数の記憶領域と仮引数 の変数領域を同一視する。従って、呼び出された関数が直接呼出し側 の変数を操作することになる。
これらの内C言語で行えるのは値呼出しのみであるが、下の例10.14で例示されているよ うに、変数の主記憶内での番地(ポインタという)を関数に引き渡すことにより参照呼出 しと同等のことも行える。
関数実行のプロセス： 関数呼出しがあると、その処理は次のような順序で進む。
(１)各々の実引数を評価。
(２)(１)の結果を対応する仮引数のデータ型に変換。
(３)(２)の結果を対応する仮引数(変数)に代入。
(値呼出し) (４) 関数の本体を実行する。実行の途中に、
(場合1)return; という文に出会うと、制御を呼出し元に戻す。(関数値なし)
(場合2)本体の実行が終了すると、制御を呼出し元に戻す。(関数値なし)
(場合3)return 式 ; という文に出会うと、 式 の値を評価し、その値をそ
の関数が本来返すべきデータ型に変換する。 そして、その結果を関数値 として制御を呼出し元に戻す。
次の例題は、
1C言語においては引数結合が値呼出しによって行われていること、そして
値呼出しを用いて参照呼出しと同等のことも行えること2
を説明している。
例題 10.14 (値呼出し,参照呼出し) 次のCプログラムを実行するとどういう出力が 得られるか？ 下の の部分に予想される出力文字列を入れよ。但し、
ここでは空白は と明示せよ。
[motoki@x205a]$ nl func-binding-parameters.c Enter 1 #include <stdio.h>
2 void call by value(int);
3 void call by reference(int *);
4 int main(void) 5 {
6 int a=1;
7 printf("%d\n", a);
8 call by value(a); /* 値呼出し*/
9 printf("%d\n", a); /* aの値は不変！*/
10 call by reference(&a); /* 参照呼出し*/
11 printf("%d\n", a); /* aの値は変わる！*/
12 return 0;
13 }
14 void call by value(int a) 15 {
16 a = 777;
17 }
10.4. パラメータの受渡し方法 —値呼出し vs. 参照呼出し— 151
18 void call by reference(int *a) 19 {
20 *a = 777;
21 }
[motoki@x205a]$ gcc func-binding-parameters.c Enter [motoki@x205a]$ ./a.out Enter
[motoki@x205a]$
(文法上の注意)
• プログラム2〜3行目, 14行目, 18行目 で関数値の型が voidと宣言されているが、こ れは関数値を返さないことを表す。
• プログラム10行目 の &a は変数 a にアクセスするためのデータ(ポインタという)を 表す。ポインタの実体は主記憶内の番地である。
• プログラム18行目, 20行目 の *a はポインタ a の指す(すなわちa番地の)記憶領域 を表す。
(考え方) プログラムの 6行目, 14行目, 18行目で同じ a という名前の変数が宣言され ているが、これらの変数はそれぞれ 5〜13行目, 14〜17行目, 18〜21行目 が有効範囲の 別々の変数として扱われる。 C言語では、
関数引数の結合が値呼出しによって行われる から、
• もし実行が8行目に移りcall by value()が次に実行されることになれば、
この関数呼び出しにより、6行目で宣言されたa の値(この時点では1のはず)が14 行目で宣言された変数(仮引数) a の初期値として引き渡され、15行目以降の関数の 処理が進む。すなわち、次の様に実行が進む。
(8行目,引数結合)
call_by_value( a );
int main(void) a
void call_by_value(int a )
a=777;
1
1 引数結合
...
(代入)...
(8行目,関数呼び出し)
call_by_value( a );
int main(void) a
void call_by_value(int a )
a=777;
1
1
...
呼出し...
(16行目,実行後)
call_by_value( a );
int main(void) a
void call_by_value(int a )
a=777;
1
777
...
...
代入(17行目,関数実行終了)
call_by_value( a );
int main(void) a
void call_by_value(int a )
a=777;
1
777
...
...
関数実行の終了 (戻り値なし、
仮引数等の局所変数の領域を解放)
=⇒ 8行目の関数実行終了後も6行目のa の値は1 のまま変わらない。
• もし実行が10行目に移りcall by reference()が次に実行されることになれば、
この関数呼び出しにより、&a の値, すなわち6行目で宣言された変数 a の番地が18 行目で宣言された変数(仮引数)a の初期値として引き渡され、19行目以降の関数の 処理が進む。すなわち、次の様に実行が進む。
(10行目,引数結合)
call_by_reference( &a );
int main(void) a
void call_by_reference(int *a )
*a = 777;
1
...
...
a の番地 引数結合
(代入)
(int型領域の先頭番地)
(10行目,関数呼び出し)
call_by_reference( &a );
int main(void) a
void call_by_reference(int *a )
*a = 777;
1
...
...
呼出し(20行目,実行後)
call_by_reference( &a );
int main(void) a
void call_by_reference(int *a )
*a = 777;
777
...
...
a の記憶している番地 の領域(*a)に 777 を代入
10.4. パラメータの受渡し方法 —値呼出し vs. 参照呼出し— 153
(21行目,関数実行終了)
call_by_reference( &a );
int main(void) a
void call_by_reference(int *a )
*a = 777;
777
...
...
関数実行の終了 (戻り値なし、
仮引数等の局所変数を解放)
=⇒ 10行目の関数実行によって6行目のa の値は 777 に変わる。
(実行結果) 結局、プログラムの
7行目では a の値は 1,
9行目では a の値は 1,
11行目では a の値は 777 になるから、実行結果は次の様になる。
[motoki@x205a]$ ./a.out Enter 1
1 777
[motoki@x205a]
番地演算子 & と間接演算子 * ：
&v · · · 変数v へのポインタ(≈番地)。
*p · · · ポインタ p の指す記憶領域、すなわちp番地の記憶領域。
=⇒変数 v があった時、*(&v) と v は同等。
参照呼出しと同等のことを行なう方法：
• 参照呼出しの仮引数は、ポインタとして宣言する。
• 関数の本体部では、参照呼出しの仮引数は間接演算子* を付けて使う。
• 関数を呼ぶ時、参照呼出しの実引数として変数等へのポインタ(i.e.番地)を与える。
□演習 10.15 (値呼出し,参照呼出し) 次のCプログラムを実行するとどういう出力が得 られるか？
#include <stdio.h>
void sub1(int, int);
int sub2(int, int);
void sub3(int *, int *);
int main(void) {
int a;
a = 0;
sub1(a, a);
printf("(sub1) %d\n", a);
a = 0;
a = sub2(a, a);
printf("(sub2) %d\n", a);
a = 0;
sub3(&a, &a);
printf("(sub3) %d\n", a);
return 0;
}
void sub1(int x, int y) {
x++;
y++;
}
int sub2(int x, int y) {
x++;
y++;
return y;
}
void sub3(int *x, int *y) {
(*x)++;
(*y)++;
}