SQL & PL/SQL

It is well known that Fibonacci series can be generated in SQL with recursion. For example:

SQL> with t(n) as
  2  (select level from dual connect by level <= 20)
  3  select *
  4  from t
  5  spreadsheet dimension by (n) measures (1 fib)
  6  (fib[n>2] order by n = fib[cv()-1] + fib[cv()-2]);

         N        FIB
---------- ----------
         1          1
         2          1
         3          2
         4          3
         5          5
         6          8
         7         13
         8         21
         9         34
        10         55
        11         89
        12        144
        13        233
        14        377
        15        610
        16        987
        17       1597
        18       2584
        19       4181
        20       6765

20 rows selected.

Similar approach can be implemented with recursive CTE or XML.

Also series can be generated with connect by + direct formula.

Also we can pre-generate required range (which does not scale very well) and do pattern matching.

with t as (select rownum id from dual connect by rownum <= 1e3)
select * from t
match_recognize
(
    order by id
    all rows per match
    pattern ((fib|{-dummy-})+)
    define fib as (id <= 2 or id = last(fib.id, 1) + last(fib.id, 2))
);

However, open question for me was if it is possible to efficiently generate Fibonacci series with _connect by_ and without direct formula.

Inefficient solution is fairly obvious - pre-generate pairs and brute-force with connect by.

with t as (select rownum id from dual connect by rownum <= 1e3),
pairs as
(
    select t1.id id1, t2.id id2
    from t t1, t t2
    where t2.id between (1 / 2) * t1.id and (2 / 3) * t1.id
    union all
    select 1, 0 from dual
    union all
    select 1, 1 from dual
)
select rownum lvl, id2 fib
from pairs
start with (id1, id2) in ((1, 0))
connect by prior id1 = id2 and prior (id1 + id2) = id1;

But this does not look very elegant and performance is even worse than pre-generating required range.