« SQL は高水準言語 | トップページ | SQL でヒストグラムを作成 »

2010年1月 3日 (日)

PostgreSQL で フィボナッチ数

使用したのは, PostgreSQL 8.4.2 です.

コード

with recursive fib(y1, y2) as (
    values (0, 1)
  union all
    select
      y2,
      y1 + y2 as y3
    from fib
)
select y1 from fib limit 20;

 

実行結果

  y1
------
    0
    1
    1
    2
    3
    5
    8
   13
   21
   34
   55
   89
  144
  233
  377
  610
  987
1597
2584
4181
(20 rows)

 

わかったこと

正確には, 再帰ではないらしいです.

Note: Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.

7.8. WITH Queries, Chapter 7. Queries, PostgreSQL 8.4.2 Documentation

色々と試していて, "iteration not recursion" の意味がわかりました. つまり, with recursive query では, 前 1 回分の計算結果しか受け取ることができません. また, 再帰箇所も 1 箇所に限定されます.

この iteration を末尾再帰と同一視してよいかはわかりませんが, iteration が末尾再帰になるのは確かでしょう.

もともと, SQL という言語は, 「再帰が使えない」という点にこだわりがあるみたいでしたので(停止性を保証することに何か意味があるらしい), 再帰が導入されたらしいと知って少々意外に思っていましたが. かなり限定的な「再帰」のようです.

データベース上で使うものだと考えれば, これはこれで良いのでしょう.

|

« SQL は高水準言語 | トップページ | SQL でヒストグラムを作成 »

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: PostgreSQL で フィボナッチ数:

« SQL は高水準言語 | トップページ | SQL でヒストグラムを作成 »