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

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

　といっても難しい話はできないのでしない。ここでは、再帰は問題のありさまを表現するための方法の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の世界を体験してみよう
	more

　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91