再帰プログラムを書いて遊んでみた
再帰を使ったプログラムを初めて見たのは、数年前にiPhoneプログラミング勉強会でフィボナッチ数列を出力するコードを見た時だった。 自分のプログラミング原点はBASIC、バリバリの手続き型言語思考の自分にとって、それはとても衝撃的な出来事で、初めて見た時はなんて芸術的なコードなんだ！と衝撃を受けた。 手続き型言語でコードを考えると、まさにやる事を頭のなかで順番にコードに置き換えて書いていく事になるのだが、再帰プログラミングでは、定義した自分自身にさらに問いただすという、自問自答の様な、合わせ鏡の様な不思議なロジック。フィボナッチ数列を出力するコードは、見様見真似で書ける様にはなったけれど、きちんと再帰を使えるには程遠い状態だ。
で、少し前からコレを解いて遊んでいた時に
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/14
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (5件) を見る
再帰でも書けますよ！という問題があったので、再帰プログラムを書く練習をしてみた。 今の自分にうってつけのブログ記事を見つけたので、練習がてらRubyでコードを書いてみた。
が、記事の回答はC#とF#という、ギターのコードなら押さえられるけれどプログラミング言語としては全く基礎知識がなかったので、なんとなく感覚で書いてみた。（なので、書いたコードに突っ込みがあればやさしく突っ込んでください。）
コードを書く時に課したルールは記事に書いてある通り、
- forループを使わない。
- 変数への再代入を使わない。
だ。そして、意識したのは、
- if文で、最終形の状態で結果をreturnする
- 最終形に至っていない時は、値を一つ取り出して最終形に1歩近づけて自らを呼び出す。
の2点。慣れれば、なんとか同じパターンを使って書くことが出来た。 関数を渡して〜系の問題は、Procオブジェクトに判定ブロックを書いて表現してみた。
果たして、ちゃんとこれで合ってるのかな？
配列の値を合計する関数 sum
配列の値の個数を返す関数 length
配列の中の値の最大値を返す関数 max
配列の値の最小値を返す関数 min
配列の全要素が条件を満たす場合は true を、一つでも条件を満たさない要素がある場合は false を返す関数 forall
配列の要素のうち一つでも条件を満たす要素があれば true を、そうでない場合は false を返す関数 exists
...その他のコードはGistに上げました。最後に、再帰処理そのものも外部化して使う、foldBack関数で書いてみました。
元となるリスト、初期値、再帰処理される内容の関数を渡すと、リストの頭から再帰処理する foldback関数
いつもとは違った手法で書いてみるのも面白いですね。
