Как эффективно создавать Фибоначчи с рекурсивным запросом - PullRequest
Новая
       41

Как эффективно создавать Фибоначчи с рекурсивным запросом

3 голосов
/ 09 марта 2020

Вы можете проверить мой код здесь: https://dbfiddle.uk/?rdbms=oracle_11.2&fiddle=61a67764f626bfadb1e9594e1ae08229

код для печати первых n терминов продолжения Фибоначчи: 

with fibo(s2,s1,n) as(
    select 1  ,1  ,1  from dual
    union all
    select s1+s2,s2,n+1 from fibo where n<12
)
select s2 from fibo;

Это работает, но это используйте, вероятно, вдвое больше памяти, чем необходимо. Каждая строка содержит n-е и n-1-е слагаемые сиквела перед выбором

Поэтому я попытался с помощью функции отставания 

with fibo(s,n) as(
    select 1,1 from dual
    union all
    select LAG(s, 1, 0) OVER ( ORDER BY s) +LAG(s, 2, 0) OVER ( ORDER BY s),n+1 from fibo where n<12
)
Select * from fibo

Но я получаю только сиквел 1. (То же самое с ведущая функция)

Я пытался понять, что происходит с этим: 

with test(s,d1,d2,n) as(
    select 1,0,0,1 from dual
    union all
    select
        2*s,LAG(s, 1, 0) OVER (a  ORDER BY s) ,
        LAG(s, 2, 0) OVER ( ORDER BY s),n+1
    from test where n<12
)
select * from test

Кажется, что лаг возвращает всегда 0. Разве нельзя использовать лаг и опережение в рекурсивном запросе? Или я делаю что-то ложное?

1 Ответ

2 голосов
/ 09 марта 2020

«Рекурсивные» запросы не являются рекурсивными, они являются итеративными.
Итерация начинается с привязки (части UNION ALL, которая не относится к CTE).
Для каждого следующего Итерация, набор результатов предыдущей итерации (с псевдонимом CTE) используется в качестве входных данных.
Итерация останавливается, когда набор результатов пуст.

В указанной вами c попытке якорь возвращает одну запись, как и каждый следующий запрос . Очевидно, что LAG (s, 2 , 0) всегда будет возвращать 0

...