Fibonacci Sequence via Recursive CTE

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Description

Using only SQL, generate the first N Fibonacci numbers using a recursive CTE. The sequence starts at F(1)=0, F(2)=1, F(3)=1, F(4)=2, ... You are given a table FibInput with a single row containing N. Return (position, fibonacci_number) for positions 1 through N, ordered by position. Table: FibInput

Column Name	Type	Description
n	INT	Number of Fibonacci values to generate

Database Schema (Inferred)

FibInput

Column Name	Example Value
n	10

Example

FibInput

n
10

Output

position	fibonacci_number
1	0
2	1
3	1
4	2
5	3
6	5
7	8
8	13
9	21
10	34

Explanation:

Use a recursive CTE carrying (n, a, b) where each step yields a and advances to (n+1, b, a+b). Terminate when n equals the value from FibInput.

Approach hint

Start with a simple approach, explain the trade-off, then move toward a cleaner or more scalable solution.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.