cp-10. 末尾再帰関数と多重再帰関数

cp-10. 末尾再帰関数と多重再 帰関数 （C プログラミング入門） URL: https://www.kkaneko.jp/pro/adp/index.html 金子邦彦 1

• https://www.kkaneko.jp/pro/adp/index.html

内容 例題１． フィボナッチ数列 例題２． McCarthyの91関数 例題３． Ackermann関数 例題４． 総和を求める末尾再帰関数 2

目標 • ２個以上の再帰呼出しを含む再帰関数（多重再 帰関数）のプログラムを読み，再帰関数につい て理解を深める • 繰り返し文を使ったプログラムを，末尾再帰関 数の形に書き直すことができるようになる 3

２個以上の再帰呼出しを含む 多重再帰関数 関数Fの本体に，Fの再帰呼出しを２個以上書いても よい． 例） ・ ハノイの塔 ・ フィボナッチ数列 ・ McCarthyの91関数 ・ Ackermann関数 4

例題１．フィボナッチ数列 • フィボナッチ数列 f 0 = 1, f1 = 1, f n = f n −1 + f n − 2 (n  1) の i 番めの数 を計算するプログラムを， 再帰関数を用いて作る 例） 1,1,2,3,5,8,13,21,34,55,89,144,.... fi 5

フィボナッチ数列 １ １ ２ ３ ５ ８ １３ ２１ ３４ 6

フィボナッチ数列 ８ ５ １ ２ ３ 7

#include <stdio.h>
#pragma warning(disable:4996)
int main()
{
int i;
int n;
int fn;
int fn1;
int fn2;
条件式
printf("n=");
scanf("%d", &n);
fn1 = 1;
fn2 = 1;
for (i=2; i<=n; i++) {
fn=fn1+fn2;
条件が成り立つ限り，
fn2=fn1;
実行されつづける部分
fn1=fn;
printf("f(%d) = %d\n", i, fn);
順番に意味がある．
}
fn1=fn;
return 0;
fn2=fn1;
}

とはしないこと

8

「繰り返し」によるフィボナッチ数列 i=2 i <= n No Yes fn=fn1+fn2; fn2=fn1; fn1=fn; printf("f(%d) = %d\n", i, fn); i++ 9

「繰り返し」によるフィボナッチ数列 n = 5 とすると i=2 i <= 5 が成立する fn = 1 + 1; fn2 = 1; fn1 = 2 i=3 i <= 5 が成立する fn = 2 + 1; fn2 = 2; fn1 = 3 i=4 i <= 5 が成立する fn = 3 + 2; fn2 = 3; fn1 = 5 i=5 i <= 5 が成立する fn = 5 + 3; fn2 = 5; fn1 = 8 i=6 i <= 5 が成立しない fi が入る fi-1 が入る fi が入る 10

#include <stdio.h>
#pragma warning(disable:4996)
int fib(int n)
{
if (n<=1) {
return 1;
}
else {
return fib(n-1)+fib(n-2);
}
}
int main()
{
int n;
int fn;
printf("Enter a number: ");
scanf("%d",&n);
fn = fib(n);
printf("Fib(%d)=%d\n",n ,fn);
return 0;
}
11

フィボナッチ数列 実行結果の例 Enter a number: 5 Fib(5)=8 12

「再帰」によるフィボナッチ数列 n <= 1 No Yes return fib(n-1) + fib(n-2); return 1; 13

「再帰」によるフィボナッチ数列 ー n=2 のときの実行順 ー n = 2 とすると 2 <= 1 No return fib(1) + fib(0); 1 <= 1 0 <= 1 yes yes return 1; return 1; 14

「再帰」によるフィボナッチ数列 ー n=3 のときの実行順 ー n = 3 とすると No 3 <= 1 return fib(2) + fib(1); No 2 <= 1 1 <= 1 return fib(1) + fib(0); 1 <= 1 0 <= 1 Yes Yes return 1; Yes return 1; return 1; 15

フィボナッチ数列の特性 • どれだけ大きな引数まで計算できるか調べてみよ う． • 引数を大きくするに従って，計算時間はどう変化 するか調べてみよう． 16

例題２． McCarthyの91関数 • McCarthyの91関数 n−10 if n 100, Mc(n) = Mc(Mc(n+11)) otherwise.          の n 番めの数を計算するプログラムを，再帰関数を 用いて作る． 17

#include <stdio.h>
#pragma warning(disable:4996)
int mc91(int n)
{
if (n>100) {
return n-10;
}
else {
return mc91(mc91(n+11));
}
}
int main()
{
int n;
int mc;
printf("Enter a number: ");
scanf("%d",&n);
mc = mc91(n);
printf("mc91(%d)=%d\n",n ,mc );
return 0;
}

18

McCarthyの91関数 実行結果の例 Enter a number: 20 mc91(20)=91 19

McCarthyの91関数の意義 • 本来のMcCarthyの91関数の定義は，再帰的な定義 • しかし，McCarthyの91関数の実際の値は単純 ⇒ １００までの値を入れて，実際に計算させると，結 果は「９１」 • McCarthyの91関数は，人工知能（プログラム理解， 自動証明，記号処理など）の，良い例題とされて きた 20

課題１．McCarthyの91関数の特性 • いろいろな数に対して， mc91 関数の返す値 を調べよ． • 次の非再帰関数m91で，mc91 関数を置き換え て，同様に調べよ． int m91(int n) { if ( n>100 ) { return n-10; } else { return 91; } } 21

例題３． Ackermann関数 • Ackermann関数 n +1 if Ack(m,n) = Ack(m−1,1) if Ack(m−1, Ack(m,n −1))              m = 0, n = 0, otherwise. を計算するプログラムを，再帰関数を用いて書く． 22

#include <stdio.h>
#pragma warning(disable:4996)
int ack(int m, int n)
{
if (m==0) {
return n+1;
}
else if (n==0) {
return ack(m-1,1);
}
else {
return ack(m-1,ack(m,n-1));
}
}
int main()
{
int n;
int m;
int a;
printf("m=");
scanf("%d",&m);
printf("n=");
scanf("%d",&n);
a = ack(m,n);
printf("Ack(%d,%d)=%d\n",m ,n ,a);
return 0;
}
23

Ackermann関数 実行結果の例 m=2 n=4 Ack(2,4)=11 24

m=1 のときのAckermann関数 • アッカーマン関数の定義 • Ack(0, n) = n +1 • Ack(m, 0) = Ack(m-1, 1) • Ack(m, n) = Ack(m-1, Ack(m, n-1)) • m=1 とすると • Ack(1, 0) = Ack(0, 1) = 1 + 1 = 2 • Ack(1, 1) = Ack(0, Ack(1, 0)) = Ack(0, 2) = 2 + 1 = 3 • Ack(1, 2) = Ack(0, Ack(1, 1)) = Ack(0, 3) = 3 + 1 = 4 数学的帰納法を使って，Ack(1, n) = n + 2 を証明することは 簡単 25

Ackermann関数の再帰の回数 • m=0 • Ack(0, 4) = 5 • Ack(0, 8) = 9 • Ack(0, 12) = 13 再帰： 1回 再帰： 1回 再帰： 1回 • Ack(1, 4) = 6 • Ack(1, 8) = 10 • Ack(1, 12) = 14 再帰： 10回 再帰： 18回 再帰： 26回 • Ack(2, 4) = 11 • Ack(2, 8) = 19 • Ack(2, 12) = 27 再帰： 65回 再帰： 189回 再帰： 377回 • m=1 • m=2 • m=3 • Ack(3, 4) = 125 • Ack(3, 8) = 2045 再帰： 10307回 再帰： 2785999回 （関数 ack を呼び出した回数） 26

Ackermann関数の意義 • Ackermann関数のプログラムは，「関数の再帰呼 び出し」を使って，書くことができた • しかし，mが少し大きくなると， Ackermann関数 の値が爆発（つまり再帰の回数も爆発）して，事 実上，計算不可能 • しかも， Ackermann関数は，「普通の繰り返し文 では書けない」ことが証明されている（このこと を，「原始帰納的でない」という） 27

課題２．Ackermann関数の特性 • どれだけ大きな引数まで計算できるか調べよ． • 引数を大きくするに従って，計算時間はどう変化 するか調べよ． 28

課題３ • フィボナッチ数列，McCarthyの91関数， Ackermann関数で，return文の直前で戻り値を 表示させ，計算の様子を調べよ． 29

例題４．総和を求める末尾再帰関数 • 総和を求める関数を，末尾再帰関数の形で書く • 末尾再帰関数については，次ページ以降で説明 30

#include <stdio.h>
#pragma warning(disable:4996)
int sum(int n, int s)
{
if (n==0) {
return s;
}
else {
return sum(n-1,n+s);
}
}
int main()
{
int n;
int souwa;
printf("Enter a number: ");
scanf("%d",&n);
souwa = sum(n, 0);
printf("sum(%d)=%d\n",n, souwa);
return 0;
}

return 文の中でのみ
再帰呼び出し

31

関数呼び出しの流れ （main 関数で n = 2 のとき） main 関数 int main() 関数呼び出し sum(n, 0); sum 関数 int sum( int n, int s ) 関数呼び出し と戻り return sum(n-1,n+s); sum 関数 int sum( int n, int s ) 関数呼び出し と戻り return sum(n-1,n+s); sum 関数 int sum( int n, int s ) 戻り return s; 32

n と s の値の変化 （main 関数で n = 2 のとき） main 関数 int main() 関数呼び出し sum(n, 0); sum 関数 int sum( int n, int s ) n=2 s=0 関数呼び出し と戻り return sum(n-1,n+s); sum 関数 int sum( int n, int s ) n=1 s=2 関数呼び出し と戻り return sum(n-1,n+s); sum 関数 int sum( int n, int s ) n=0 s=3 戻り return s; 33

末尾再帰関数とは • 再帰関数の中で，一番最後（つまり return 文な ど）で，ただ１度だけ，その本体の再帰呼び出し を行うもの • 再帰呼び出しを行ったら，その関数がすぐに終わる • 再帰呼び出しの結果（戻り値）を得たら，その関数自体 の戻り値として，直接戻す • 「末尾再帰関数」と，「繰り返し文を使ったプロ グラム（再帰関数の無いもの）」とは，互いに， 簡単に書き直せる 34

再帰関数と末尾再帰関数 • 再帰関数で，末尾再帰関数に書き直すことができ るもの • 整数の総和，階乗，フィボナッチ数列など • 再帰関数で，末尾再帰関数に書き直すことができ ないもの • Ackermann関数など 35

末尾再帰の計算の方法 • 途中結果を引数に与えて，関数の再帰呼び出しを 行う． • 最後の再帰呼び出しでは，与えられた途中結果を 最終結果として返す 例） 2+0 → s(2,0) ↓ 1+2 → s(1,2) ↓ → s(0,3) →3 36

課題４ 次の階乗関数を，末尾再帰の形に書き直せ．また，書 き直した階乗関数を使う main 関数を書き，正しく動作 することを確認すること． int factorial( int n ) { int result = 1; int i; for( i = 1; i <= n; i++ ) { result = i * result; } return result; } 37

課題４について • 末尾再帰で無い例： return n * factorial( n-1 ); return factorial( n-1 ) * n; いずれも，factorial(n-1) の返り値を使って，n との掛け算を行っている • 末尾再帰にするには： 途中結果を引数に含めること 例）return factorial( n-1, n*s ); 38

課題５ • フィボナッチ数列を末尾再帰の形で書け． ヒント： 一歩前の途中結果 f k −1 と，ニ歩前の途 中結果 f k −2 の二つを引数に加えて，再帰呼び出 しする． 39