最近は高等学校でもプログラミングを教えるみたいなので、
高校生でもわかるようにやさしくに解説していきます。
まず始めに 1 から 10 までの合計を求めるプログラムを考えます。
(define (sum-ex1) 55)
55 ってわかってるからね。そのまま書いちゃった。
実行してみよう。
gosh> (sum-ex1) 55
ハイ正解！
(define (sum-ex2) (+ 1 2 3 4 5 6 7 8 9 10))
さすがに解答直書きは気が引けるというそこの君も
実行してみよう。
gosh> (sum-ex2) 55
ハイ正解！
いいよいいよー。みんなとてもいいね！
さてここで、いつも 10 までの合計を求めたいわけじゃなくて、
20 までとか、100 までとか、もしかすると1億までとか
もっともっと大きな数字まで、合計を求めたいとしたら、どうしたら良いと思う？
先ほど示した例だと、100 までならなんとかなりそうだけども、
1 億までとかになるとすごく大変そうだよね？
そこでどうするかについて考えていこう。
(define (sum-ex3 n) (if (<= n 0) 0 (+ n (sum-ex3 (- n 1)))))
正解のコードはこんなかんじになります。
判断と、繰り返しループ(再帰)を使います。
急に難しくなったって？ 心配無用。これから解説していくよ。
まず判断から。判断は if を使います。
(if <条件> <条件が成立するときやる手続き> <条件が成立しないときやる手続き>)
と書きます。
Scheme では、if 文は必ず値を返します。
手続きを書いた場合は手続きの返却値、値を書いた場合はその値そのものを返します。
例を示しましょう。
a と b を比較して大きい方を 10 倍する
ju-bai という手続き(=プログラム)を考えよう。
(define (ju-bai a b)
(if (> a b)
(* a 10)
(* b 10)))if 文をつかってこんな感じに書けるね。
実行してきちんと動くか試してみよう。
(ju-bai 2 5)
これは引数 a に 2 を、引数 b に 5 を渡して ju-bai 手続きを実行するってことだね。
予想では a は 2、b は 5 だから、b の 5 を 10 倍して 50 という結果を返すはずだね。
gosh> (ju-bai 2 5) 50
正しい結果が得られたね。
じゃあ、 a に 7、b に 3 を渡したらどうなるかな？
今度は a のほうが大きいから 7 を 10 倍して、70 を結果として返すはずだね。
gosh> (ju-bai 7 3) 70
プログラムは正しい結果を返しているね。
if 文の使い方わかったかな？
プログラムを何か条件によって違う動きをさせたいとにき、 if 文を使うんだ。
プログラムがいつも同じ動きしか出来ないとつまんないよね。 if 文、これを覚えてね。
さて、次に 5 まで合計したいときは、
(sum-ex3 5)
と書くことに決めよう。10 まで合計したいなら、
(sum-ex3 10)
10000 まで合計したいなら、
(sum-ex3 10000)
と書くわけだね。ここまではいいかな?
この 5 や 10 や 10000 のことを「引数」といいます。
この引数はプログラムでは、n という変数に値が格納されます。
つぎにループ(再帰)は、
(define (<手続き名> <引数>)
(if <終了条件>
<終了のときに実行する手続き>
<終了でないときに実行する手続き>
))と書きます。
引数は 1 つだけではなくて、必要によって複数個にしたりも出来ます。
引数が 0 個の場合もあります。手続きのところには値を書いても良いです。
プログラムから、
(sum-ex3 0) = 0
になるのはわかるかな?
(sum-ex3 1)
はどうなるだろう。
(sum-ex3 1) = (+ 1 (sum-ex3 0))
になるのはわかるかな。
つまり、
(sum-ex3 1) = (+ 1 (sum-ex3 0)) = (+ 1 0) = 1
こうなるね。
じゃあ、引数を 5 まで順々に増やしてみるよ。
(sum-ex3 5) = (+ 5 (sum-ex3 4)) (sum-ex3 4) = (+ 4 (sum-ex3 3)) (sum-ex3 3) = (+ 3 (sum-ex3 2)) (sum-ex3 2) = (+ 2 (sum-ex3 1)) (sum-ex3 1) = (+ 1 (sum-ex3 0)) (sum-ex3 0) = 0
n = 5 のときは n = 4 を使って
n = 4 のときは n = 3 を使って
n = 3 のときは n = 2 を使って
.....
自分自身を再定義しているわけだね。
これを「再帰的定義」っていいます。
さっきのプログラムは再帰的に
自身のプログラムを定義しているわけだね。
再帰の考え方をもう少し説明すると、
手続き sum-ex3 の引数に 4 を与えると、1 から 4 まで合計した結果を返すわけだね。
gosh> (sum-ex3 4) 10
だね。この手続きの引数に 4 を与えると、常に 10 という結果を返します。
朝でも、昼でも、夜でも、明日でも、明後日でも、１か月後でも、１年後でも、１０年後でも
引数の値が同じならこの結果は変わらないんだ。
春でも夏でも秋でも冬でも晴れの日でも曇りの日でも雨の日でも雪の日でも、
引数の値が同じなら、かならずいつも同じ結果を返すよ。
なにかの気まぐれで値が変わっちゃうなんてことも絶対ないです。
言い方を変えてみると、手続きは「状態」を持たないってことだね。
「状態」を持つ僕ら人間だと、「今日は憂鬱だから値を二倍にしちゃおっかな」とか、
「今ちょっと忙しいから今日は 0 でいいや」みたいになっちゃうよね。
でも手続きは「状態」を持たないので、与える引数が同じなのに値がコロコロ変化することは
無いわけだね。
ちょっと難しい言葉なんだけども、これを「参照透過性」って言います。
Scheme でプログラミングする上でとても大切な「性質」なので覚えてね。
引数を変えてたくさん書いてみるよ。
(sum-ex3 1) = 1 (sum-ex3 2) = 3 (1 + 2) (sum-ex3 3) = 6 (1 + 2 + 3) (sum-ex3 4) = 10 (1 + 2 + 3 + 4) (sum-ex3 5) = 15 (1 + 2 + 3 + 4 + 5) (sum-ex3 6) = 21 (1 + 2 + 3 + 4 + 5 + 6) (sum-ex3 7) = 28 (1 + 2 + 3 + 4 + 5 + 6 + 7) ...
これをじっと眺めていると、なにか見えてくるものがないかな？
もうちょっと書き方を変えてみようか。
(sum-ex3 7) は 7 に (sum-ex3 6) を足せばいいよね？ (sum-ex3 6) は 6 に (sum-ex3 5) を足せばいいよね？ (sum-ex3 5) は 5 に (sum-ex3 4) を足せばいいよね？ (sum-ex3 5) は 5 に (sum-ex3 4) を足せばいいよね？ (sum-ex3 4) は 4 に (sum-ex3 3) を足せばいいよね？ (sum-ex3 3) は 3 に (sum-ex3 2) を足せばいいよね？ (sum-ex3 2) は 2 に (sum-ex3 1) を足せばいいよね？ (sum-ex3 1) は 1 に (sum-ex3 0) を足せばいいよね？ (sum-ex3 0) は 0 だよ。
なんか数字の部分に一定の決まり事みたいのが見えてこない？
これを法則性といって、これをプログラムでそのまま書いちゃおう！
ってのを「再帰プログラミング」とか「再帰的定義」って言います。
さらに、それじゃあ引数が n だったらどうなるかな？
(sum-ex3 n) は n に (sum-ex3 (- n 1)) を足せばいいよね？ ただし n が 0 以下のときは 0
こうやって書けるね。
最初は具体的な値で考えて、じゃあ n だったらどうなるんだろう？
って考える方法はプログラミングだけじゃなくて数学でもよくやる手法なんだ。
これを「一般化」といいます。
前に示したプログラムをもう一回見てみよう。
(define (sum-ex3 n) (if (<= n 0) 0 (+ n (sum-ex3 (- n 1)))))
プログラムの最後のあたりをよーく見てね。
ほら、ついさっき説明した事がそのままプログラムとして書いてあるよね？
わかるかな？
再帰の部分はちょっと難しかったかも知れないけれども
そのうち慣れるから心配はいらない。すぐ理解できるようになるから安心して。
では実行してみよう。
gosh> (sum-ex3 10) 55
引数に 10 を指定しているので 1 から 10 までの合計を返したよ。
引数を変えれば、いろんな合計が計算できるようになったね。
つまり、1 から n までの合計を求める事ができるわけだね。
gosh> (sum-ex3 100) 5050
gosh> (sum-ex3 10000) 50005000
さて、実はこのプログラムには、あまり大きな値を引数にすると、
実はきちんと計算できないかもしれないという欠点があるんだ。
複雑なコンピュータの内部事情の話は省くけれども、
今はそういうものだと思っておいてもらえれば十分です。
