【神の】クエリでフィボナッチ数列【数列】

## 【目的】
メジャーな数学題材からクエリ、アルゴリズムを学ぶ。

## 【環境】

| SQLServer | SQLCMD | PowerShell |
| ---- | ---- | ---- |
| 2017 | 14.0.1000.169 | 5.1.18362.145 |
設定はデフォルト。

## 【フィボナッチ数列】
[フィボナッチ数 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0 "フィボナッチ数 - Wikipedia")
恐らく最も有名な数列。しばしば [ドラマ](https://ameblo.jp/kannagi0823/entry-11756393458.html "米TVドラマ「TOUCH」はスゴイ！！") にも登場するし [自然界](https://style.nikkei.com/article/DGXNASFK2901O_Z20C13A7000000/ "ヒマワリ・稲妻…自然界を司る神秘的な「数式」") で観察されることでも知られている。
そんな神の数列をクエリで書いてみる訳だけど、それだけでは簡単過ぎるので、ついでにカンマ区切り連結にも触れる。

## 【実装 1】

```SQL
DECLARE @Max    INT = 22;       -- 求める数列数

;WITH [CTE_Fib] AS (            -- フィボナッチ数列CTE
    SELECT
          1     [Seq]           -- 連番
        , 0     [Cur]           -- 現在位置の値
        , 1     [Pre]           -- 一つ前の値
    UNION ALL
    SELECT
          [Seq] + 1
        , [Cur] + [Pre]         -- 一つ前のレコードと二つ前のレコードの値を足す
        , [Cur]
    FROM [CTE_Fib]
    WHERE   [Seq] < @Max
)
SELECT [Cur] FROM [CTE_Fib] ORDER BY [Seq]
;
GO
```
一つ前のレコードと二つ前のレコードの値を足した結果を現在のレコードの値としている。
少々紛らわしいのが、二つ目の SELECT文は一つ前のレコードを指している点。
だから、[Cur] は一つ前のレコードの値であり、[Pre] は二つ前のレコードの値となる。

工夫した点としては、先頭レコードにダミーとして持たせている一つ前のレコードの値である 1。結果として、これで 2レコード目の値が 1 となる。
実行結果は以下。

```SQL
Cur
-----------
          0
          1
          1
          2
          3
          5
          8
         13
         21
         34
         55
         89
        144
        233
        377
        610
        987
       1597
       2584
       4181
       6765
      10946

(22 行処理されました)
```

## 【PowerShell】
答え合わせに PowerShell でも書いてみる。但し、上記のような縦の出力は冗長なのでカンマ区切り連結で横に並べる。

```PowerShell
PS C:\Users\user> $fibArray = @(0, 1)
PS C:\Users\user> 3..22 | %{$fibArray += ($fibArray[-1] + $fibArray[-2])}
PS C:\Users\user> $fibArray -join ", "
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
```

PowerShell だと簡単だよなぁ。配列の添え字に負数を指定すると後ろからの順番になる仕様が利いている。これがないと、`$fibArray[$fibArray.Length - 1]` みたいな冗長な記述になってしまう。
カンマ区切り連結も簡単だし。

## 【実装 2】
やはり数列ならカンマ区切りで横に並べた方が見やすいだろってことで、クエリでも実装してみる。
メジャーな方法としては `XML FOR`句だろう。
[FOR XML (SQL Server) - SQL Server _ Microsoft Docs](https://docs.microsoft.com/ja-jp/sql/relational-databases/xml/for-xml-sql-server?view=sql-server-2017 "FOR XML (SQL Server) - SQL Server _ Microsoft Docs")
ヘルプを見てもカンマ区切り連結に結びつかない。
本来は  XML形式の文字列を生成する為のものだが、列を連結して行を返す仕様を利用することになる。実装例は以下。

```SQL
DECLARE @Max    INT = 22;       -- 求める数列数

;WITH [CTE_Fib] AS (            -- フィボナッチ数列CTE
    SELECT
          1     [Seq]           -- 連番
        , 0     [Cur]           -- 現在位置の値
        , 1     [Pre]           -- 一つ前の値
    UNION ALL
    SELECT
          [Seq] + 1
        , [Cur] + [Pre]
        , [Cur]
    FROM [CTE_Fib]
    WHERE   [Seq] < @Max
)
, [CTE_Xml]([Str]) AS (         -- カンマ区切り連結CTE
    SELECT ', ' + LTRIM(STR([Cur])) FROM [CTE_Fib] ORDER BY [Seq] FOR XML PATH('')
)
SELECT STUFF([Str], 1, 2, '') FROM [CTE_Xml]
;
GO
```
決め打ちで前カンマを付加しているので、最後に `STUFF`関数で先頭カンマを削除している。
実行結果は以下。

```SQL
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946                                                                                                                                                 

(1 行処理されました)
```

## 【実装 3】
今回のように CTE を利用しているケースなら、そのついでにカンマ区切りも、って考え方もできる。実装例は以下。

```SQL
DECLARE @Max    INT = 22;       -- 求める数列数

;WITH [CTE_Fib] AS (            -- フィボナッチ数列CTE
    SELECT
          1     [Seq]           -- 連番
        , 0     [Cur]           -- 現在位置の値
        , 1     [Pre]           -- 一つ前の値
        , CONVERT(VARCHAR(MAX), 0)
                [Str]           -- カンマ区切り連結文字列
    UNION ALL
    SELECT
          [Seq] + 1
        , [Cur] + [Pre]         -- 一つ前のレコードと二つ前のレコードの値を足す
        , [Cur]
        , [Str] + ', ' + LTRIM(STR([Cur]) + [Pre])
    FROM [CTE_Fib]
    WHERE   [Seq] < @Max
)
SELECT [Str] FROM [CTE_Fib] WHERE [Seq] = @Max
;
GO
```

この場合、カンマ区切りで連結していく過程のレコードも生成されていしまう。その為、`WHERE`句で最後のレコードだけを抽出している。
実行結果は以下。

```SQL
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946                                                                                                                                                 

(1 行処理されました)
```

カンマ区切り連結にも対応できる。そう、CTE ならね。

## 【実装 4】
変数に格納しても良いなら以下のような方法も。

```SQL
DECLARE @Max    INT          = 22;  -- 求める数列数
DECLARE @Fib    VARCHAR(MAX) = '';  -- フィボナッチ数列格納変数

;WITH [CTE_Fib] AS (            -- フィボナッチ数列CTE
    SELECT
          1     [Seq]           -- 連番
        , 0     [Cur]           -- 現在位置の値
        , 1     [Pre]           -- 一つ前の値
    UNION ALL
    SELECT
          [Seq] + 1
        , [Cur] + [Pre]
        , [Cur]
    FROM [CTE_Fib]
    WHERE   [Seq] < @Max
)
SELECT @Fib += IIF(@Fib = '', '', ', ') + LTRIM(STR([Cur]))
FROM [CTE_Fib]
ORDER BY [Seq]
;
PRINT @Fib
GO
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
```