ゼロからはじめてみる日本語プログラミング「なでしこ」(42) ギターのFコード的存在の「再帰処理」を使って幾何学模様を描いてみよう

今回はプログラミングで一つの壁とも言われる『再帰』について紹介します。再帰が分かると、より複雑なプログラムを作ることができます。再帰の例として、フィボナッチ数列を求めたり、幾何学模様を描いたりしてみましょう。再帰を使うと、以下のような幾何学模様を容易に記述できます。

幾何学模様を描いたところ

『再帰』とは何だろう？

プログラミングの参考書を読んでいると、時々『再帰』や『再帰処理』という言葉を見つけます。再帰というのは、関数の中でその関数自身を呼び出すテクニックのことです。関数の中で、その関数自身を呼び出すと聞いても、なんだかピンと来ない方が多いようです。

ちなみに、ギター初心者の人は、すべての弦を押さえるFコードがなかなか弾けず、多くの人が挫折するため、「Fコードの壁」と呼ばれています。この『再帰』は、さながら、プログラミング初心者にとって「再帰の壁」と呼んでも良いでしょう。

例えば、1から10までを順に足していくプログラムは、再帰処理使って書くと、以下のように記述することができます。Webブラウザでなでしこを実行できる簡易エディタ（こちら:)で試してみてください。

# 関数を定義 --- (*1)
●(Nを)再帰加算とは
　　もし、N<0ならば、0で戻る。
　　それは、N + ((N-1)を再帰加算) # --- (*2)
ここまで

# 関数を呼び出す --- (*3)
10を再帰加算して表示。

実行すると、以下のように、1から10までを足した値、55が表示されます。

再帰的に1から10を加算するプログラム

プログラムの(＊1)の部分で『再帰加算』という名前の関数を定義します。そして、(＊3)の部分でこの関数を呼び出します。
そして、ポイントとなるのは、(＊2)の部分です。関数『再帰加算』の中で関数『再帰加算』を呼び出しているのです。
その際『(N-1)を再帰加算』のように、引数が全く同じ値ではなく、異なる値の引数を指定している点がポイントです。

(＊3)の部分では、引数を10で『再帰加算』を呼び出していますから、(＊2)の部分では、引数の値が9で『再帰加算』が呼び出されます。そして、同じように、8、7、6...と順に『再帰加算』が呼び出されます。とは言え、そのままでは、永遠に関数を呼び出してしまいます。そのため、『再帰加算』の開始直後で、引数Nが0以下ならば、0を答えとして戻すようにして、改めて再帰加算を呼び出さないようにしています。これが『再帰』を使うコツです。永遠に関数を呼び出すことがないように、引数に条件をつけて、再帰で呼び出さないようにします。

雰囲気としては、関数の中で、関数を呼び出し、その関数の中でまた関数を呼び出し、その中でまた関数を呼び出し・・・と、マトリョーシカのような構造になります。

再帰加算を呼び出した時の構造 - マトリョーシカに似ている

フィボナッチ数を求めよう

上記の数値の加算と似たプログラムですが、次にフィボナッチ数を求めるプログラムを作ってみましょう。

フィボナッチ数というのは、1, 1, 2, 3, 5, 8, 13, 21, 34, 55...のように、1つ目と2つ目の数を足した値が3つ目の値になるという数のことです。そして、このフィボナッチ数は自然界によく見られることで知られており、花ビラの数はフィボナッチ数です。また、らせん状に並んだヒマワリの種を数えていくと、それはフィボナッチ数となっています。フィボナッチ数というのは非常に面白いです。

それでは、フィボナッチ数を求めるプログラムを作ってみましょう。

# --- (*1) ---
●(Nの)フィボナッチ数計算とは
　　もし、N < 1ならば、1で戻る。
　　N1 = (N-1)のフィボナッチ数計算
　　N2 = (N-2)のフィボナッチ数計算
　　(N1 + N2)で戻る。
ここまで

# --- (*2) ---
Nを-1から15まで繰り返す
　　Nのフィボナッチ数計算して表示。
ここまで。

同じく簡易エディタで、実行ボタンを押すと、以下のように表示されます。

フィボナッチ数を計算するプログラム

プログラムの(＊1)で再帰的にフィボナッチ数を計算する関数を定義します。フィボナッチ数とは、1つ前と2つ前の二つの値を足したものです。そのため、再帰的に1つ前の値と2つ前の値を取得し、それを足し合わせたものが、今回の値となります。そのため、再帰を使うと非常に簡単にフィボナッチ数を求めるプログラムを記述できます。

そして、(＊2)では、繰り返し構文を利用して、実際に17個のフィボナッチ数を計算して表示します。

幾何学模様を描いてみよう

ここまで、再帰について考えてきました。とは言え、数字が画面に出るだけではそれほど面白くありません。そこで、なでしこのタートルグラフィックスの機能を利用して、再帰を利用したプログラムを作ってみましょう。

【L字を組み合わせた図形】

最初にL字状の図形を組み合わせた幾何学模様を見てみましょう。

L字を再帰的に描画した図形

この図形を描画するのが、以下のプログラムです。同じく、なでしこ3簡易エディタ（タートルグラフィックス版）で実行してみましょう。

●(Nの)L字描画
　　もし、N＜10ならば、戻る。
　　Nだけカメ進む
　　90だけカメ右回転。
　　Nだけカメ進む。
　　90だけカメ左回転。
　　Nだけカメ進む。
　　90だけカメ右回転。
　　Nだけカメ進む。
　　90だけカメ右回転。
　　N×2だけカメ進む。
　　90だけカメ右回転。
　　N×2だけカメ進む。
　　90だけカメ右回転。
　　(N * 0.5)のL字描画。
ここまで。

カメ作成。
10にカメ速度設定。
青色にカメペン色設定。
8回
　　70のL字描画。
　　45だけカメ右回転。
ここまで。

上記のプログラムでは、関数『L字描画』を再帰的に呼び出すことで、複雑な図形を描画した飢えに、繰り返し構文で、8回、45度回転させて描画することで、面白い図形を描画しました。カメが少しずつ描画していくので、とても面白いことでしょう。

【ブロッコリーもどき（フラクタルツリー）】

次に、タートルグラフィックスのお題では必ず出てくる『フラクタルツリー』を描画してみましょう。今回は、パラメータを少し調整することで、木というより、ブロッコリーのような絵を描いてみました。

ブロッコリーもどき

この図形を描くプログラムは、以下の通りです。

# 描画のための設定
カメ作成。
2にカメ速度設定。
RGB(30,90,30)にカメペン色設定 
[320, 390]にカメ起点移動。
1にカメペンサイズ設定。
A=23
R=0.83
50だけカメ進む。
50で枝描画。
カメ非表示。

●(長さで)枝描画とは
　　もし、長さ＜9ならば、戻る。
　　＃左側の枝
　　Aだけカメ左回転。
　　長さだけカメ進む
　　(長さ×R)で枝描画。
　　長さだけカメ戻る
　　Aだけカメ右回転。
　　＃右側の枝
　　Aだけカメ右回転。
　　長さだけカメ進む
　　(長さ×R)で枝描画。
　　長さだけカメ戻る
　　Aだけカメ左回転。
ここまで

『フラクタル』というのは、自己相似的という意味で、図形の一部を取り出すと、それ自体が全体の形と似ている成り立ちをしているものを言います。

上記のプログラムを見てみると分かりますが、関数『枝描画』では、Vの形の図形を再帰的に描画するようになっています。つまり、左側の枝と右側の枝と二回、再帰的に『枝描画』を呼び出します。

まとめ

以上、今回は再帰について紹介しました。再帰を使った図形を見ると、非常に複雑に見えます。しかし、今回紹介したプログラムをよく見てみると、その中で定義した関数自体はとても簡単なものです。簡単な仕組みであっても、再帰を使うことで複雑な処理を行うことができるのです。これが『再帰』の力です。

今回、後半で紹介したように、タートルグラフィックスでお絵かきしながら、再帰する関数を作る練習をしてみると良いでしょう。ちなみに、もし再帰の終了条件を入れ忘れると、再帰が深くなりすぎるとメモリを大量に消費します。その場合、Webブラウザが不安定になることがありますが、ページをリロードしたり、ページを閉じると問題が解決します。簡易エディタの【仮保存】ボタンを押すと、一時的にプログラムを保存できるので活用してみてください。