再帰を用いた繰り返し計算の仕組み、数学の再帰的定義
とSchemeプログラムの対応関係、関数の繰り返し回数
の理解
【学習内容の構成】
1. 線形再帰的プロセス：階乗計算を例に、式が展開・
収縮する再帰の動作
2. 反復的プロセス：カウンタと部分積を用いた伸び縮
みのない繰り返し計算
3. ユークリッドの互除法：余りを求める操作の繰り返
しによる最大公約数の計算
4. ステップ実行：DrSchemeのstepperによる計算過程
の可視化と繰り返し回数の確認
• 前提：Schemeの基本文法（define、cond）、リスト
操作（first、rest、empty?）
• 意義：再帰の実行過程の理解、アルゴリズムの効率性
への意識
2
• 再帰を使った，繰り返し計算
• 数学の「再帰的定義」と，Scheme
プログラムの関係
• 繰り返し回数
• 関数は「何回繰り返して」実行され
るか
本日の内容
3
12-1 繰り返し計算
4
• 階乗
• 「n - 1 の階乗」に n を足すことを繰り返す
• ユークリッドの互除法
• m と n の最大公約数を求めるために，「割った余
りを求めること」を，余りが０になるまで繰り返
す
繰り返しの例
5
12- 2 パソコン演習
6
• 資料を見ながら，「例題」を行ってみる
• 各自，「課題」に挑戦する
• 自分のペースで先に進んで構いません
パソコン演習の進め方
7
• DrScheme の起動
プログラム → PLT Scheme → DrScheme
• 今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
8
• 階乗を計算する関数 ! を作り，実行す
る
• 次の方針でプログラムを作成する
n > 0 のとき，n! = n × (n-1)!
例） 6! = 6×5!
例題１． 階乗
9
• n = 0 のとき
1!=n
• n > 0 のとき
)!1(! −= nnn
階乗
10
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
;;! : number -> number
;;to compute n*(n-1)*...*2*1
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題２に進んでください
(! 3)
(! 4)
「例題１．階乗」の手順
11
「例題１．階乗」の実行結果
12
まず，Scheme のプログラムを
コンピュータに読み込ませている
13
これは，
(! 4)
と書いて，n の値を
4 に設定しての実行
実行結果である「24」が
表示される
14
!
24
入力
出力
4
入力は数値
出力は数値
入力と出力
15
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; Example: (! 4) = 24
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
n! は (n-1)! を計算して，n を掛ける
0! = 1 である
! 関数
16
1. n = 0 ならば： → 終了条件
1 → 自明な解
2. そうで無ければ：
– 「n - 1 の階乗」に n をかける
⇒ 結局，1 から n までのかけ算を繰り返
す
階乗
17
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
自明な解
終了条件
階乗
18
(= n 0)
(* n (! (- n 1)))
Yes
No
1 が自明の解
終了条件
19
• ! の内部に ! が登場
• ! の実行が繰り返される
例： (! 5) = (* 5 (! 4))
(! 4) = (* 4 (! 3))
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
階乗
20
• 関数 ! （例題１）について，実行結果に至る過程
を見る
• (! 3) から 6 に至る過程を見る
• DrScheme の stepper を使用する
21
例題２．ステップ実行
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
1. 次を「定義用ウインドウ」で，実行しなさい
• Intermediate Student で実行すること
• 入力した後に，Execute ボタンを押す
;;! : number -> number
;;to compute n*(n-1)*...*2*1
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
(! 3)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
• 理解しながら進むこと
☆ 次は，例題３に進んでください
例題１と同じ
「例題２．ステップ実行」の手順
22
! の「n」は「3」で置き換わる
23
「(= 3 0)」は「false」で
置き換わる
24
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる
25
「(- 3 1)」は，「2」で
置き換わる
26
! の「n」は「2」で置き換わる
27
「(= 2 0)」は「false」で
置き換わる
28
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる
29
「(- 2 1)」は，「1」で
置き換わる
30
n は 1 である
31
「(= 1 0)」は「false」で
置き換わる
32
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる
33
「(- 1 1)」は，「0」で
置き換わる
34
n は 0 である
35
「(= 0 0)」は「true」で
置き換わる
36
「(cond [true 式Ｘ] [else 式Ｙ])」は
「式Ｘ」で置き換わる
37
「(* 1 1)」は，「1」で
置き換わる
38
「(* 2 1)」は，「2」で
置き換わる
39
「(* 3 2)」は，「6」で
置き換わる
40
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
最初の式
実行結果
コンピュータ内部での計算
(! 3) から 6 が得られる過程の概略
41
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
(! 3)
= (cond
[(= 3 0) 1]
[else (* 3 (! (- 3 1)))])
= (cond
[false 1]
[else (* 3 (! (- 3 1)))])
= (* 3 (! (- 3 1)))
= (* 3 (! 2))
この部分は
(! 3) から 6 が得られる過程の概略
42
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
(! 3)
= (cond
[(= 3 0) 1]
[else (* 3 (! (- 3 1)))])
= (cond
[false 1]
[else (* 3 (! (- 3 1)))])
= (* 3 (! (- 3 1)))
= (* 3 (! 2))
この部分は
これは，
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
の n を 3 で置き換えたもの
(! 3) から 6 が得られる過程の概略
43
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
「(! 3)」 が膨張して
「(* 3 (* 2 (* 1 (! 0))))」
になる
基本的な計算式への展開
「(* 3 (* 2 (* 1 (! 0))))」
が収縮して６になる
演算の実行
(! 3) から 6 に至る過程
44
例 (! 3) ⇒ (* 3 (* 2 (* 1 (! 0))))
• 基本的な計算式へ展開
再帰の呼び出し回数（＝ステップ
数ともいう）に比例して成長する
⇒ 「線形再帰」の名前の由来
線形再帰的プロセス
45
(! 3)
= ...
= (* 3 (! 2))
= ...
= (* 3 (* 2 (! 1)))
= ...
= (* 3 (* 2 (* 1 (! 0))))
= ...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
n=3 のとき，
4回繰り返して実行される
①
②
③
④
! が繰り返される回数
46
(! 4)
= ...
= (* 4 (! 3))
= ...
= (* 4 (* 3 (! 2)))
= ...
= (* 4 (* 3 (* 2 (! 1))))
= ...
= (* 4 (* 3 (* 2 (* 1 (! 0)))))
= ...
= (* 4 (* 3 (* 2 (* 1 1))))
= (* 4 (* 3 (* 2 1)))
= (* 4 (* 3 2))
= (* 4 6)
= 24
n=4 のとき，
5回繰り返して実行される
①
②
③
④
⑤
! が繰り返される回数
47
• 階乗を計算する関数 ! を作り，実行す
る
• 次の方針でプログラムを作成する
n > 0 のとき，1 から開始して，1 × 2
×・・・×n を計算する
例） (! 6) = 1 × 2 × 3 × 4 × 5 × 6
例題３． 反復的プロセスでの階乗
48
• n! の計算
1. まず，1 に 2 を掛ける
2. 次に，3 を掛ける
3. ・・・
4. n に達するまで続ける
反復的プロセスでの階乗
49
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (! n)
(factorial 1 1 n))
(define (factorial product counter max)
(cond
[(> counter max) product]
[else (factorial (* counter product)
(+ counter 1)
max)]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題４に進んでください
(! 4)
(! 10)
(! 20)
「例題３．反復的プロセスでの階乗」の手順
50
まず，Scheme のプログラムを
コンピュータに読み込ませている
51
これは，
(! 4)
と書いて，n の値を
4 に設定しての実行
実行結果である「24」が
表示される
52
!
24
入力
出力
4
入力は数値
出力は数値
入力と出力
53
54
! 関数
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (! n)
(factorial 1 1 n))
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
product ← counter・product
counter ← counter + 1
counter: 1 から n まで数えるカウンタ
product: 部分積（計算の途中結果）
とする．
product ← counter・product
counter ← counter + 1
を繰り返す．counter が n に達すると
n!が求まる
反復的プロセスでの階乗
55
1. counter > n ならば：→ 終了条件
product → 自明な解
2. そうで無ければ：
次を実行する
product ← counter・product
counter ← counter + 1
反復的プロセスでの階乗
56
57
反復的プロセスでの階乗
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (! n)
(factorial 1 1 n))
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
終了条件
自明な解
(> counter n)
(factorial (* counter product)
(+ counter 1)
n)
Yes
No
product が自明の解
終了条件
58
• factorial の内部に factorial が登場
• factorial の実行が繰り返される
例： (factorial 6 4 10) = (factorial 24 5 10)
(factorial 24 5 10) = (factorial 120 6 10)
59
例題４．ステップ実行
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
例題４．ステップ実行
• 関数 ! （例題３）について，実行結果に至る過程
を見る
• (! 4) から 24 に至る過程を見る
• DrScheme の stepper を使用する
60
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
1. 次を「定義用ウインドウ」で，実行しなさい
• Intermediate Student で実行すること
• 入力した後に，Execute ボタンを押す
(define (! n)
(factorial 1 1 n))
(define (factorial product counter max)
(cond
[(> counter max) product]
[else (factorial (* counter product)
(+ counter 1)
max)]))
(! 4)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
• 理解しながら進むこと
☆ 次は，例題５に進んでください
例題３と同じ
「例題４．ステップ実行」の手順
61
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
最初の式
実行結果
コンピュータ内部での計算
(! 4) から 24 が得られる過程の概略
62
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
product, counter の
値が変化する
・counter
→ 繰り返し回数
・product
→ 部分積
product
counter
max
(! 4) から 24 が得られる過程の概略
63
例 (! 3) = (factorial 1 1 3)
= (factorial 1 2 3)
= (factorial 2 3 3)
= (factorial 6 4 3)
• 線形再帰的プロセスのような伸び縮みは無い
• 関数を再帰的に呼び出す各ステップで計算が実
行される
伸び縮み無し
各ステップで，
product と counter
に関する計算が
実行される
反復的プロセスの特徴
64
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
(factorial 1 1 4)
= (cond
[(> 1 4) 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (cond
[false 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (factorial (* 1 1) (+ 1 1) 4)
= (factorial 1 (+ 1 1) 4)
= (factorial 1 2 4)
この部分は
(factorial 1 1 4) から (factorial 1 2 4) が得られる過程
65
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
(factorial 1 1 4)
= (cond
[(> 1 4) 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (cond
[false 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (factorial (* 1 1) (+ 1 1) 4)
= (factorial 1 (+ 1 1) 4)
= (factorial 1 2 4)
この部分は
これは，
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
の counter を 1 で，product を 1 で，n を 4 で置き換えたもの
(factorial 1 1 4) から (factorial 1 2 4) が得られる過程
66
(! 4)
= ...
= (* 4 (! 3))
= ...
= (* 4 (* 3 (! 2)))
= ...
= (* 4 (* 3 (* 2 (! 1))))
= ...
= (* 4 (* 3 (* 2 (* 1 (! 0)))))
= ...
= (* 4 (* 3 (* 2 (* 1 1))))
= (* 4 (* 3 (* 2 1)))
= (* 4 (* 3 2))
= (* 4 6)
= 6
(! 4)
= (cond
[(= 4 0) 1]
[else (* 4 (! (- 4 1)))])
= (cond
[false 1]
[else (* 4 (! (- 4 1)))])
= (* 4 (! (- 4 1)))
= (* 4 (! 3))
この部分は
これは，
(define (! n)
(cond
[(= n 0) 1]
[else (* n (! (- n 1)))]))
の n を 4 で置き換えたもの
(! 4) から (* 4 (! 3)) が得られる過程
67
(! 4)
= (factorial 1 1 4)
= ...
= (factorial 1 2 4)
= ...
= (factorial 2 3 4)
= ...
= (factorial 6 4 4)
= ...
= (factorial 24 5 4)
= ...
= 24
n=4 のとき，
5回繰り返して実行される
①
②
③
④
⑤
factorial が繰り返される回数
68
• 次のプログラムでは，square は何回実行されるか
(define (square x)
(* x x))
(define (total-square x)
(cond
[(empty? x) 0]
[else (+ (square (first x)) (total-square (rest x)))]))
例題５．繰り返し回数
69
実行結果の例
(total-square (list 10 20 30))
1400
• square は，リストの要素数だけ実行される
繰り返し回数
70
• ユークリッドの互除法を使って，２つ
の整数 m, n から，最大公約数を求める
プログラム my-gcd を作り，実行する
例） 180, 32 のとき： 4
• ユークリッドの互除法を用いる
例題６．最大公約数の計算
71
• ２つの整数 m, n の最大公約数:
（m, n は正または０）
• n = 0 なら
最大公約数は m
• n ≠ 0 なら
最大公約数は， 「m を n で割った余り」 と n の最大公
約数に等しい
ユークリッドの互除法
72
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題７に進んでください
(mygcd 180 32)
「例題６．最大公約数の計算」の手順
73
まず，Scheme のプログラムを
コンピュータに読み込ませている
74
これは，
(my-gcd 180 32)
と書いて，m の値を 180 に，
n の値を 32 に設定しての実行
実行結果である「4」が
表示される
75
my-gcd
4
入力
出力
180 32
入力は，２つの数値
出力は数値
入力と出力
76
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
my-gcd 関数
77
1. n = 0 ならば： → 終了条件
m → 自明な解
2. そうで無ければ：
(1) n
(2) m を n で割った余り
の２数の最大公約数を求める．
以上のことを，n が０に達するまで繰り返す
最大公約数の計算
78
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
自明な解
終了
条件
79
(= n 0)
(my-gcd n
(remainder m n)
Yes
No
m が自明の解
終了条件
80
• my-gcd の内部に my-gcd が登場
• my-gcd の実行が繰り返される
例： (my-gcd 180 32)
= (my-gcd 32 20)
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
最大公約数の計算
81
• 関数 my-gcd （例題６）について，実行結果に至
る過程を見る
• (my-gcd 180 32) から 4 に至る過程を見る
• DrScheme の stepper を使用する
82
例題７．ステップ実行
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
1. 次を「定義用ウインドウ」で，実行しなさい
• Intermediate Student で実行すること
• 入力した後に，Execute ボタンを押す
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
(my-gcd 180 32)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
• 理解しながら進むこと
☆ 次は，課題に進んでください
例題６
と同じ
「例題７．ステップ実行」の手順
83
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
実行結果
コンピュータ内部での計算
最初の式
(my-gcd 180 32) から 4 が得られる過程の概略
84
(my-gcd 180 32)から (my-gcd 32 20) が得られる過程
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
(my-gcd 180 32)
= (cond
[(= 32 0) 180]
[else (my-gcd 32
(remainder 180 32))])
= (cond
[false 180]
[else (my-gcd 32
(remainder 180 32))])
= (my-gcd 32
(remainder 180 32))
= (my-gcd 32 20)
この部分は
180 を 32 で割った余り
は 20
85
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
(my-gcd 180 32)
= (cond
[(= 32 0) 180]
[else (my-gcd 32
(remainder 180 32))])
= (cond
[false 180]
[else (my-gcd 32
(remainder 180 32))])
= (my-gcd 32
(remainder 180 32))
= (my-gcd 32 20)
この部分は
これは，
(define (my-gcd m n)
(cond
[(= n 0) m]
[else (my-gcd n
(remainder m n))]))
の m を 180 で，n を 32 で置き換えたもの
(my-gcd 180 32) から (my-gcd 32 20) が得られる
過程
86
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
①
②
③
④
⑤
⑥
m=180, n=32 のとき，
6回繰り返して実行される
my-gcd が繰り返される回数
87
12-3 課題
88
• 関数 my-gcd （授業の例題６）に関する問題
• (my-gcd 210 66) から 6 が得られる過程の概略を
数行程度で説明しなさい
• DrScheme の stepper を使うと，すぐに分かる
課題１
89
• バックの中のコインの合計を求める関数
sum-coin についての問題
• 下記の空欄を埋めて，関数 sum-coins の定義を終
えなさい．実行結果も報告しなさい
• sum-coins は，コインの個数のリストと，コイン
の金額のリストの２つのリストを入力とする
;; Contract: sum-coins : a-list-of-numbers a-list-of-numbers -> number
;; Example: (sum-coins (list 23 0 5 7) (list 1 5 10 25)) = 248
(define (sum-coins a b)
(cond [( ) ]
[else (+ (* ( ) ( ))
( ( ) ( )))]))
課題２
90
• ここにあるのは「間違い」の例です．同じ間
違いをしないこと
１．(= a empty) は間違い
⇒ a がリストのとき、(= a empty) はエラーです．
「=」は数値の比較には使えるが，リスト同士
の比較には使えないものと考えて下さい
正しくは，(empty? a) です
課題２のヒント
91
• 関数 my-gcd （授業の例題６）に関する問題
• m, n の最大公約数を，ユークリッドの互除法で求
めた場合と，次ページに示すような方法で求めた場
合とで，関数の繰り返し回数を比較し，自分なりの
考察を加えて報告しなさい
課題３．繰り返し回数
92
(define (first-divisor n m i)
(cond
[(= i 1) 1]
[else (cond
[(and (= (remainder n i) 0)
(= (remainder m i) 0)) i]
[else (first-divisor n m (- i 1))])]))
(define (gcd-structural n m)
(first-divisor n m (min n m)))
1. まず，n と m の小さい方を変数 i に入れる．
2. i が n と m の両方を割れれば i の値を返し，終了．
3. i の値を1小さくして2へ．
→ n と m は変わらない．i が変化
「i で割り切れるかを調べながら，
i を１減らす」ことを，割り切れる
まで繰り返す
93
• 「エラトステネスのふるい」の原理に基づ
いて100以下の素数を求めるプログラムを作
りなさい
課題４．エラトステネスのふるい
94
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
２×２
２×３
２×４
２×５
まず，２の倍数を消す
エラトステネスのふるい (1/4)
95
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
３×２
次に，３の倍数を消す
３×３
エラトステネスのふるい (2/4)
96
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
次に，５の倍数を消す
（「４の倍数」は考えない．
それは，「４」がすでに消えているから）
５×２
エラトステネスのふるい (3/4)
97
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
以上のように，２，３，５・・・の倍数を消す．
１０（これは１００の平方根）を超えたら，この操作を止める
（１００以下で，１１，１３・・・の倍数はすでに消えている）
エラトステネスのふるい (4/4)
98
