フィボナッチ数を計算するプログラムの作成、木構
造再帰と反復的プロセスの比較による計算効率の理
解
【学習内容の構成】
1. フィボナッチ数の定義：f₀=0, f₁=1, fₙ=fₙ₋₁+fₙ₋₂
で定まる数列
2. 木構造再帰（例題1）：生成的再帰による素直な
実装、計算の冗長性
3. 反復的プロセス（例題2）：累積変数を用いた効
率的な実装
• 前提：Schemeの基本文法、cond式、再帰の概念
• 意義：同じ問題に対する異なるアルゴリズムの性
能差の体感
2
17-1 フィボナッチ数
3
１ １ ２ ３ ５ ８ １３ ２１ ３４
フィボナッチ数
4
１
２
３
５
８
フィボナッチ数
5
• 生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
の i 番めの数 を計算するプログラムを作る
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
)1(
,1
,0
21
1
0
+=
=
=
−−
nfff
f
f
nnn
i
f
フィボナッチ数
6
)1(
,1
,0
21
1
0
+=
=
=
−−
nfff
f
f
nnn
フィボナッチ数
7
17-2 パソコン演習
8
• 資料を見ながら，「例題」を行ってみる
• 各自，「課題」に挑戦する
• 自分のペースで先に進んで構いません
パソコン演習の進め方
9
• DrScheme の起動
プログラム → PLT Scheme → DrScheme
• 今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
10
• 生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
の i 番めの数 を計算するプログラムを作る
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
)1(
,1
,0
21
1
0
+=
=
=
−−
nfff
f
f
nnn
i
f
例題１．フィボナッチ数
11
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
(define (fibo n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[else (+ (fibo (- n 1)) (fibo (- n 2)))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題２に進んでください
(fibo 5)
(fibo 6)
(fibo 7)
「例題１．フィボナッチ数」の手順
12
実行結果の例
13
fibo
3
入力
出力
4
入力は数値
出力は数値
入力と出力
14
(define (fibo n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[else (+ (fibo (- n 1)) (fibo (- n 2)))]))
フィボナッチ数
15
1. n = 0 ならば： → 終了条件
0 → 自明な解
2. n = 1 ならば： → 終了条件
1 → 自明な解
3. そうで無ければ：
– (fibo (- n 2)) と (fibo (- n 1)) を足す
⇒ 結局，fibo の実行を繰り返す
フィボナッチ数
16
(fibo 4)から
3 が得られる過程の概略 (1/2)
(fibo 4)
= …
= (+ (fibo (- 4 1))
(fibo (- 4 2)))
= …
= (+ (+
(fibo (- 3 1))
(fibo (- 3 2)))
(fibo (- 4 2)))
= …
= (+ (+ (+
(fibo (- 2 1))
(fibo (- 2 2)))
(fibo (- 3 2)))
(fibo (- 4 2)))
= …
= (+ (+ (+
1
0)
(fibo (- 3 2)))
(fibo (- 4 2)))
17
(fibo 4)から
3 が得られる過程の概略 (2/2)
= …
= (+ (+
1
1)
(fibo (- 4 2)))
= …
= (+ 2
(+
(fibo (- 2 1))
(fibo (- 2
2))))
= …
= (+ 2
(+ 1 0))
= …
= 3
18
(fibo 4)
(fibo 3)
(fibo 2)
(fibo 1)
(fibo 0)
(fibo 1)
(fibo 2)
(fibo 1)
(fibo 0)
fibo の計算パターンは、木構造再帰である
19
フィボナッチ数
• 関数 fibo は，n > 1 のとき，fibo を2
回呼び出す
例） (fibo 10) を計算するために (fibo
9) と (fibo 8) を計算している
• 計算パターンは，木構造再帰(tree
recursion)をなす
• 樹木状をなす （前ページ）
20
• フィボナッチ数
の i 番めの数 を計算するプログラムを作る
• 例題１よりも繰り返し回数が少なくなるよう
に工夫する
)1(
,1
,0
21
1
0
+=
=
=
−−
nfff
f
f
nnn
i
f
例題２．「反復的プロセス」での
フィボナッチ数
21
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
(define (fibo n)
(fibo-iterate 1 0 n))
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a (- counter 1))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，課題に進んでください
(fibo 5)
(fibo 6)
(fibo 7)
「例題２．反復的プロセスでのフィボナッチ数」の手順
22
実行結果
23
(define (fibo n)
(fibo-iterate 1 0 n))
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a (- counter 1))]))
「反復的プロセス」でのフィボナッチ数
24
1. まず，f
1
(=1), f
0
(=0) から始め
る
2. 次に，f
0
, f
1
を使って，f
2
を求
める
3. ・・・
4. n に達するまで続ける
「反復的プロセス」でのフィボナッチ数
25
a=1, b=0 から開始して，
a ← a + b
b ← a
を繰り返す．
「反復的プロセス」でのフィボナッチ数
26
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a (- counter
1))]))
a ← a + b
b← a
終了条件
27
(fibo 4)
= (fibo-iterate 1 0 4)
= ...
= (fibo-iterate 1 1 3)
= ...
= (fibo-iterate 2 1 2)
= ...
= (fibo-iterate 3 2 1)
= ...
= (fibo-iterate 5 3 0)
= ...
= 3
a, b, counter の
値が変化する
(fibo 4) から 3 が得られる過程の概略
28
• 例題１
• 木構造的な再帰
• 計算が冗長
例） (fibo 4) の計算では，(fibo 2), (fibo 1), (fibo 0) が
繰り返し現れる
• 例題２
• 反復的プロセス
• 例題１ではあった「冗長な計算」が、例題２で無い
まとめ
29
17-3 課題
30
• 例題１と例題２のフィボナッチ数のプログラムを，性
能の面から比較せよ
• 例題１と例題２のプログラムについて，(fibo 6) を計算する
ために，例題１の fibo, 例題２の fibo-iterate が何回繰り返し
実行されるか数えよ
• 例題１と例題２のプログラムを，DrScheme のstepper で実
行し，最終的な結果が得られるまでに「next」ボタンを押し
た回数（置き換えが起こった回数）を数えてみよ
• これは，(fibo 3), (fibo 4), (fibo 5), (fibo 6) について行え
課題１
31
