内容
例題１． フィボナッチ数列
例題２． McCarthyの91関数
例題３． Ackermann関数
例題４． 総和を求める末尾再帰関数
2
目標
•２個以上の再帰呼出しを含む再帰関数（多重再
帰関数）のプログラムを読み，再帰関数につい
て理解を深める
•繰り返し文を使ったプログラムを，末尾再帰関
数の形に書き直すことができるようになる
3
２個以上の再帰呼出しを含む
多重再帰関数
関数Fの本体に，Fの再帰呼出しを２個以上書いても
よい．
例）
・ハノイの塔
・ フィボナッチ数列
・McCarthyの91関数
・Ackermann関数
4
•フィボナッチ数列
のi番めの数 を計算するプログラムを，
再帰関数を用いて作る
例） 1,1,2,3,5,8,13,21,34,55,89,144,....
)1(
,1
,1
21
1
0
nfff
f
f
nnn
i
f
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);
}
return 0;
}
順番に意味がある．
fn1=fn;
fn2=fn1;
とはしないこと
条件が成り立つ限り，
実行されつづける部分
条件式
8
「繰り返し」によるフィボナッチ数列
i = 2
i <= n
fn=fn1+fn2;
fn2=fn1;
fn1=fn;
printf("f(%d) = %d\n", i, fn);
i++
Yes
No
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 1;
return fib(n-1) + fib(n-2);
13
「再帰」によるフィボナッチ数列
ーn=2 のときの実行順 ー
n = 2 とすると
2 <= 1 No
return fib(1) + fib(0);
1 <= 1
return 1;
yes
0 <= 1
return 1;
yes
14
「再帰」によるフィボナッチ数列
ーn=3 のときの実行順 ー
n = 3 とすると
3 <= 1 No
return fib(2) + fib(1);
2 <= 1 No
return fib(1) + fib(0);
1 <= 1
return 1;
Yes
1 <= 1
return 1;
Yes
0 <= 1
return 1;
Yes
15
フィボナッチ数列の特性
•どれだけ大きな引数まで計算できるか調べてみよ
う．
•引数を大きくするに従って，計算時間はどう変化
するか調べてみよう．
16
•McCarthyの91関数
のn 番めの数を計算するプログラムを，再帰関数を
用いて作る．
otherwise.))11((
,100 if10
)( nMcMc
nn
nMc
17
例題２． McCarthyの91関数
#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関数
を計算するプログラムを，再帰関数を用いて書く．
.))1,(,1(
,0)1,1(
,01
),(
otherwisenmAckmAck
nifmAck
mifn
nmAck
22
例題３． Ackermann関数
#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 再帰： 1回
•Ack(0, 8) = 9 再帰： 1回
•Ack(0, 12) = 13 再帰： 1回
•m=1
•Ack(1, 4) = 6 再帰： 10回
•Ack(1, 8) = 10 再帰： 18回
•Ack(1, 12) = 14 再帰： 26回
•m=2
•Ack(2, 4) = 11 再帰： 65回
•Ack(2, 8) = 19 再帰： 189回
•Ack(2, 12) = 27 再帰： 377回
•m=3
•Ack(3, 4) = 125 再帰： 10307回
•Ack(3, 8) = 2045 再帰： 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 のとき）
sum 関数
int sum( int n, int s )
main 関数
int main()
sum(n, 0);
関数呼び出し
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 のとき）
sum 関数
int sum( int n, int s )
main 関数
int main()
sum(n, 0);
関数呼び出し
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;
戻り
n = 2
s = 0
n = 1
s = 2
n = 0
s = 3
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
課題５
•フィボナッチ数列を末尾再帰の形で書け．
ヒント： 一歩前の途中結果 と，ニ歩前の途
中結果 の二つを引数に加えて，再帰呼び出
しする．
1k
f
2k
f
39
![[image]](https://www.kkaneko.jp/info/kanekomail.png)