【3/18〜】Amazon、VMwareが語る『クラウドの未来』 スラッシュドット    はてなブックマーク  Yahoo!ブックマークに登録  印刷

第4回　再帰とデータ型の話をしよう

山下 伸夫
株式会社タイムインターメディア

2009/2/16

関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう（編集部）
- PR -

　まず、再帰の話をしよう。

　といっても難しい話はできないのでしない。ここでは、再帰は問題のありさまを表現するための方法の1つだ思うことにする。

　では具体的な問題を考えてみよう。

階乗を計算する関数

　階乗を計算する関数を考えてみよう。

ある正整数をnとすると、n!（nの階乗）とはn×(n-１)×…×2×1のことである

　階乗を計算するときの計算方法はいろいろありそうだが、

n!＝n×(n-１)×…×2×1＝ｎ×(ｎ-１)!

つまり、

n!は(ｎ-１)!にnを掛けたものである

となる。ここから、計算方法は、

n!を計算するには、一歩手前の(n-１)!が分かったとして、それにnを掛ける

と考えることができるのである。nからn!への関数をfactとすると、この計算はHaskellでは、

fact n = n * fact (n - 1)

と表現できる。

　ここでfactを定義するのにfactを使っている。このような定義の仕方を再帰的定義という。少し奇妙な感じがするかもしれない。fact nを定義するのにfact (n-1)、つまりfact nとは別のものを使っていると思えば、この感覚は治まるかもしれない。

　さて、実際に計算してみよう。この定義をfact.hsというファイルに保存して、ghciにロードする。

$ ghci fact.hs
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( fact.hs, interpreted )
Ok, modules loaded: Main.
*Main>
fact.hs

　例えば、9!を計算をしてみよう。プロンプトにfact 9を入力すると、

*Main> fact 9
*** Exception: stack overflow

と表示される。

　何が起こったのだろう。もう一度、

fact n = n * fact (n - 1)

という定義を見てみると、fact 9の値を計算するには、9の値とfact 8の値が必要で、fact 8の値を計算するには、8の値とfact 7の値が必要、fact 7の値を計算するに、7の値とfact 6の値が必要、fact 6の値を計算するには……と、どこまでいってもきりがないのである。

　階乗の値は最初の定義では1以上のnについて意味があるので、n≦1であるようなnの一歩手前というのは存在しない。また、1!は1であるとしておくのが妥当なので、n＝1のときは特別扱いして、factの定義を以下のようにしよう。

fact :: Integer -> Integer -> Integer
fact n | n > 1     = n * fact (n - 1)
       | n == 1    = 1
       | otherwise = undefined

　今度はちゃんと動くはずだ。

階段の昇り方

　もう1つ問題を考えよう。

階段を1度に1段または1段飛しで（つまり1度に2段）昇るものとする。階段の段数を与えられたとき、その昇り方が何通りあるかを表現する関数を定義せよ

　これも前節と同じように考えると簡単に定義できる。

　何度か昇って、いまn段目にいるとすると、直前には(n-1)段目にいたか、(n-2)段目にいたかのどちらかである。ということは、n段目に到達する昇り方の数は、(n-1)段目への昇り方の数と(n-2)段目への昇り方の数の和になるはずだ。

　n段目への昇り方の数をstepWays nと表現すると、

stepWays n = stepWays (n-1) + stepWays (n-2)

となる。これだけでは先ほどと同じようなエラーになってしまうので、もう少し考えよう。

  • いま1段目にいるとすると、直前にいたのは0段目
  • いま0段目にいるとすると、直前というのはなく、そこにいるわけだから0段目への昇り方は1通りと考えるのが妥当

というわけで、stepWaysは次のように定義できる。

stepWays :: Integer -> Integer
stepWays n | n >  1    = stepWays (n-1) + stepWays (n-2)
           | n == 1    = stepWays 0
           | n == 0    = 1
           | otherwise = undefined

　では、5段目まで昇ってみよう。

*Main> stepWays 5
8

　図で説明したように5段目までなら8通りの昇り方があることが計算できている。

　このセクションおよび前セクションでの考え方は、典型的な再帰の考え方である。課題を解く関数の再帰的定義が、課題を素直に表現したものになっていることに注目してほしい。

 
1/3

Index
再帰とデータ型の話をしよう
Page1
階乗を計算する関数
階段の昇り方
  Page2
計算の効率
データ型の話をしよう
論理値型
数値型
  Page3
文字と文字列
リスト
文字列は文字のリスト

のんびりHaskell
　Coding Edgeお勧め記事
いまさらアルゴリズムを学ぶ意味
コーディングに役立つ！ アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
Zope 3の魅力に迫る
Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
貧弱環境プログラミングのススメ
柴田 淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
Haskellプログラミングの楽しみ方
のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
ちょっと変わったLisp入門
Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91

Coding Edge フォーラム 新着記事

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

RSSフィード

＠IT 新着記事

スキルアップ／キャリアアップ（JOB@IT）

＠IT Special -PR-
仮想環境の構築とデータ保護の特効薬？！
実績と信頼性の高いパッケージで安心運用
New！
仮想環境のバックアップもこれまでどおり
「まるごと取ってまるごと戻す」簡単運用
おばかアプリ選手権、第４弾開催中！！
ムダにカッコよくてくだらない作品求ム！
社内ファイルサーバを“クラウド”に統合
VPN直結「クラウド型ストレージ」を紹介
その数、なんと400台以上！ グループ内
サーバの「統合管理」によるメリットは？
美人!? まあまあ？ 気になる いやし系!!
PV急増で「美人時計」がとった手段とは？
.NET編集長が実践する「技術情報検索術」
サンプル・コードを簡単に探す“技”は？
進化を続ける富士通ストレージETERNUS DX
製品開発者の自信を裏付けるものとは何か
運用管理の課題を“2つの観点”から分析
ユーザー満足度の高い「仮想環境」とは？

→＠IT Special ヘ

お勧め求人情報

キャリアアップ　〜JOB＠IT
＠IT Special -PR-
◆ 　 おばかアプリ選手権、第４弾開催中！！
ムダにカッコよくてくだらない作品求ム！
◆ 　 社内ファイルサーバを“クラウド”に統合
VPN直結「クラウド型ストレージ」を紹介
◆ 　 Twitterのアカウントはなぜ突破された？
メールによる新手の攻撃手法とその対策

◆ 　 もう仮想化のお試しフェイズは終わりだ！
Hyper-V 2.0が基幹システムも仮想化
◆ 　 美人!? まあまあ？ 気になる いやし系!!
PV急増で「美人時計」がとった手段とは？
◆ 　 クライアント企業から求められる人材
⇒IT技術と経営戦略を併せ持つ「戦略家」

◆ 　 .NET編集長が実践する「技術情報検索術」
サンプル・コードを簡単に探す“技”は？
◆ 　 業務効率と情報セキュリティ対策を両立！
手間なく確実に機密情報を守る方法とは？
◆ 　 直属上司が海外にいるのエンジニアに見る
【実例】場所に捉われないワークスタイル

◆ 　 「仮想化工房」のマイスターが選んだのは
VMware、Hyper-V、そしてVirtageだった！
◆ 　 進化を続ける富士通ストレージETERNUS DX
製品開発者の自信を裏付けるものとは何か
◆ 　 運用管理の課題を“2つの観点”から分析
ユーザー満足度の高い「仮想環境」とは？

◆ 　 【CTC事例】約30の基幹システムを統合！
膨大なバッジジョブを制御した方法は？
◆ 　 仮想化すればコストは削減できるか？
仮想化に必要な「3つの視点」を解説する
◆ 　 その数、なんと400台以上！ グループ内
サーバの「統合管理」によるメリットは？

→＠IT Special ヘ