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

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

2009/2/16

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

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

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

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

階乗を計算する関数

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

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

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

n!=n×(n-1)×…×2×1=n×(n-1)!

つまり、

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

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

n!を計算するには、一歩手前の(n-1)!が分かったとして、それに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.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

Coding Edge 記事ランキング

本日 月間