# Fibonacci function or sequence

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:

1 1 2 3 5 8 13 21 34 55 89 ...


Write the shortest code that either, in accordance to the standard rules:

• Generates the Fibonacci sequence without end.

• Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

• Given n calculates the first n terms of the sequence

You may use standard forms of input and output.

For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});
else console.log(body);
});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();

languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body {
text-align: left !important;
display: block !important;
}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• I am sort of waiting for a response like "f", 1 byte, in my math based golf language. Commented Aug 11, 2020 at 11:57
• @ChrisJesterYoung can we use 1.0 are 1 only? Commented May 11, 2022 at 2:45
• @NumberBasher 1.0 is fine. Commented May 20, 2022 at 19:10
• What about 1.3? Commented Aug 28, 2022 at 15:10
• Am I allowed to start the sequence with 0, 1? Commented Oct 11, 2022 at 3:41

# Rust, 100 characters

|n|{let mut a=1u64;let mut b=1u64;let mut s=vec![a,b];for _ in 0..n {let t=b;b=a+b;a=t;s.push(b);}s}


A closure that takes an integer n as input and returns a vector of the first n items of the Fibonacci sequence.

• You could shave off a few bytes given the fact that you don't have to return all the Fibonacci numbers, just the nth one. Commented Sep 23, 2018 at 15:06

# Pip, 10 9 bytes

(The language is newer than the question.)

W1o:y+YPo


Outputs infinite Fibonacci numbers on separate lines, beginning with 1. Try it online!

### Explanation

The easy part is W1, which uses 1 as an always-truthy condition to create an infinite while loop.

We use two built-in variables, o and y, which are initially 1 and "", respectively. Note that an empty string in arithmetic contexts is treated as 0. At each iteration, y will hold the smaller of two consecutive Fibonacci numbers, and o will hold the larger.

The loop body is a single expression: o:y+YPo. It's important to know that Pip evaluates a binary-operator expression by first evaluating the left operand, then the right operand, then performing the operation. So, using the third iteration as an example (y is 1, o is 2):

• The left operand of : (the assignment operator) is o; we'll compute y+YPo and then assign that value to o.
• The left operand of + is y, which is currently 1.
• The right operand of + is YPo. YP is a unary operator that takes the value of its operand--here, o, which is 2--prints it, and yanks it into y. So when YPo is evaluated, 2 is printed, y is set to 2, and the expression evaluates to 2.
• + adds 1 and 2 and gives 3.
• : assigns 3 to o.

The end result is that 2 is printed, y becomes 2, and o becomes 3. Repeat ad infinitum.

# Little Man Computer, 45 bytes, 8 instructions

Note: both answers only work up to $$\ f(15) = 987 \$$, as the maximum value for an integer in LMC is $$\ 999 \$$.

The first solution generates Fibonacci numbers 'indefinitely':

LDA 7
STA 7
SUB 8
STA 8
OUT
BRA 0
DAT 1


and is assembled into RAM as

507 108 307 208 308 902 600 001


## 86 bytes, 14 instructions

The second solution returns the Fibonacci number at the index given (0-based indexing):

INP
STA 0
LDA 12
STA 12
SUB 14
STA 14
LDA 0
SUB 13
BRP 1
LDA 14
OUT
DAT 1
DAT 1


...which is assembled into RAM as:

901 300 512 114 312 214 314 500 213 801 514 902 001 001


You can test these on the online simulator here.

# Python 3, 43 Bytes

a,c=0,0;b=1
while 1:print(a);c=a+b;a=b;b=c

• Note that Python has a swap statement to avoid having to use an extra variable: a,b=b,a+b. Also, there are plenty of shorter Python answers already posted. Commented Dec 17, 2018 at 20:21
• Also, 0 isn't supposed to be included in this challenge. Commented Dec 18, 2018 at 1:30

# Pure, 66 bytes

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end);


Try it online!

Prints until TIO stops it or the heat death of the universe, whatever comes first.

### How:

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end); // Anonymous lambda;
using system;                                                      // Import system functions
do                                                    // Infinite loop
(printf"%Zd\n")                                     // Print bigints + linefeed
(f 1L 1L                             // Declare f with 2 bigint args
// starting with 1
with f a b=                 // with f(a,b) being
a:f b(a+b)       // a list from a until f(b,(a+b));
&      // transformed into a stream
// to prevent overflowing
end);


# R, 37 bytes

Prints the n'th term using the closed form.

https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

function(n,s=5^.5)round((s/2+.5)^n/s)


Try it online!

# Awk, 35 bytes

BEGIN{for(y=1;z=x+y;y=z)print(x=y)}


Try it online

# \/\/>, 9 bytes

:@+1}:nau


Outputs infinitely starting from 0, with each number on a new line.

### Explanation:

:           Dupe top of stack
@          Rotate the top three elements
+         Add the top two elements
1}       Push a 1 to the bottom of the stack
:nau   Print the top number with a trailing newline


# Keg, 10 bytes

01{:. ,:"+


Endlessly outputs numbers separated by spaces

# How it works

0    Pushes 0
1    Pushes 1
{    Begins an endless while loop
:.   Outputs the top item of the stack
,   Outputs a space
:"   Duplicates the top item of the stack and puts it at the bottom
+    Adds the top two numbers of the stack


Try it Online!

# x86 Machine Code (ELF format) - 484 bytes

This program will calculate fibonacci digits until there is no memory left, so you might want to process the output to get Nth one you are looking for.

Offset(h) 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

00000000  7F 45 4C 46 01 01 01 00 00 00 00 00 00 00 00 00  .ELF............
00000010  02 00 03 00 01 00 00 00 C0 80 04 08 34 00 00 00  ........Ŕ€..4...
00000020  00 00 00 00 00 00 00 00 34 00 20 00 02 00 28 00  ........4. ...(.
00000030  00 00 00 00 01 00 00 00 00 00 00 00 00 80 04 08  .............€..
00000040  00 00 00 00 E4 01 00 00 00 10 00 00 05 00 00 00  ....ä...........
00000050  00 10 00 00 01 00 00 00 00 00 00 00 00 90 04 08  ................
00000060  00 00 00 00 00 00 00 00 00 00 10 00 06 00 00 00  ................
00000070  00 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00000080  51 B9 00 90 04 08 88 01 31 C0 BA 01 00 00 00 EB  Qą......1Ŕş....ë
00000090  03 51 89 C1 31 C0 89 C3 43 B0 04 CD 80 31 C0 99  .Q‰Á1Ŕ‰ĂC°.Í€1Ŕ™
000000A0  42 59 C3 00 00 00 00 00 00 00 00 00 00 00 00 00  BYĂ.............
000000B0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
000000C0  31 C0 99 42 B9 03 90 04 08 C6 41 01 0A C6 41 02  1Ŕ™Bą....ĆA..ĆA.
000000D0  01 C6 41 03 01 3A 71 03 0F 84 FF 00 00 00 3A 71  .ĆA..:q..„˙...:q
000000E0  03 74 26 80 41 03 05 0F B6 41 03 6B C0 08 00 41  .t&€A...¶A.kŔ..A
000000F0  04 8A 41 04 E8 87 FF FF FF 80 69 04 30 C6 41 03  .ŠA.č‡˙˙˙€i.0ĆA.
00000100  01 83 E9 03 3A 71 03 75 DA 8A 41 04 E8 6F FF FF  ..é.:q.uÚŠA.čo˙˙
00000110  FF 3A 71 06 0F 84 BA 00 00 00 0F B6 41 05 88 41  ˙:q..„ş....¶A..A
00000120  06 0F B6 41 07 88 41 05 0F B6 41 07 00 41 06 C6  ..¶A..A..¶A..A.Ć
00000130  41 07 00 3A 71 06 0F 84 88 00 00 00 C6 41 07 01  A..:q..„....ĆA..
00000140  FE 49 06 3A 71 06 0F 84 78 00 00 00 C6 41 07 02  ţI.:q..„x...ĆA..
00000150  FE 49 06 3A 71 06 0F 84 68 00 00 00 C6 41 07 03  ţI.:q..„h...ĆA..
00000160  FE 49 06 3A 71 06 0F 84 58 00 00 00 C6 41 07 04  ţI.:q..„X...ĆA..
00000170  FE 49 06 3A 71 06 74 4C C6 41 07 05 FE 49 06 3A  ţI.:q.tLĆA..ţI.:
00000180  71 06 74 40 C6 41 07 06 FE 49 06 3A 71 06 74 34  q.t@ĆA..ţI.:q.t4
00000190  C6 41 07 07 FE 49 06 3A 71 06 74 28 C6 41 07 08  ĆA..ţI.:q.t(ĆA..
000001A0  FE 49 06 3A 71 06 74 1C C6 41 07 09 FE 49 06 3A  ţI.:q.t.ĆA..ţI.:
000001B0  71 06 74 10 FE 41 08 FE 41 09 FE 49 06 0F B6 41  q.t.ţA.ţA.ţI..¶A
000001C0  06 88 41 07 C6 41 06 01 83 C1 03 3A 71 06 0F 85  ..A.ĆA...Á.:q..…
000001D0  46 FF FF FF 3A 71 03 0F 85 01 FF FF FF B3 00 31  F˙˙˙:q..….˙˙˙ł.1
000001E0  C0 40 CD 80                                      Ŕ@Í€

• no explanation?
– qwr
Commented Feb 11, 2023 at 0:31
• @qwr Considering I have been 15 when this post has been made, I'm afraid that I would have to put as much effort into reverse engineering it as everyone else :) Commented Feb 11, 2023 at 5:29

# Brain-Flak, 3634 32 bytes

({}(())){({}[()]<(({})<>{})>)}<>


Outputs the nth number of the zero indexed Fibonacci sequence (F(0) = 1, F(1) = 1, etc.)

Try it online!

# Gol><>, 7 bytes

12K+:N!


Byte knocked off courtesy of JoKing

Try it online!

9 bytes

01T2K+:Nt


Outputs forever with newlines

Try it online!

# JVM Byte Code, 79 bytes

The byte count given is for a complete class file that defines a class Code containing single static method Code which implement Fibonacci. A hex dump of the file is given below.

0000000: cafe babe 0003 002d 0004 0100 0428 4929  .......-.....(I)
0000010: 4901 0004 436f 6465 0700 0200 2000 0300  I...Code.... ...
0000020: 0000 0000 0000 0100 0800 0200 0100 0100  ................
0000030: 0200 0000 1800 0400 0100 0000 0c03 045a  ...............Z
0000040: 6084 00ff 1a9d fffa ac00 0000 0000 00    ..............


A helper class is required to invoke the function.

class Test {
public static void main(String[] args){
for(int i = 0; i < 20; i++){
System.out.println(Code.Code(i));
}
}
}


Try it online!

The disassembly of the class file with javap -c shows actual byte code implementation of Fibonacci. This requires only 11 bytes, the rest of the 79 bytes in the class file are various header tables that can't be omitted.

class Code {
static int Code(int);
Code:
0: iconst_0
1: iconst_1
2: dup_x1
4: iinc          0, -1
8: ifgt          2
11: ireturn
}


# Pyth, 13 bytes

A(Z1)#HA(H+HG


Try it online!

### Explanation

A(Z1)#HA(H+HG

(Z1)           : The tuple (0, 1)
A               : Assign the first value of the tuple to G and the second to H
#          : Loop until error statement
H         : Print H
(H+HG   : The tuple (H, H + G)
A        : Assign the first value of the tuple to G and the second to H


# Ral, 27 bytes

11=,1*:0*+1=0=1/-:1:+:+?0*.


Try it online!

## Go 114113 106 chars

I'm sure this can be improved but I'd like to share my approach using the closed-form expression to calculate Fibonacci numbers.

package main
import(."fmt"
."math")
func main(){for i:=0.0;i<31;i++{Printf("%.0f\n",Pow(Phi,i)/Sqrt(5));}}


# Actually, 16 bytes

"1,"◙01W;a+;◙',◙


Try it online!

# GAS x86-64 for Linux (Machine code), 76 68 bytes

### Loop-free, because I thought it would be a fun idea. GCC 10.1.

Note/warning: for this to work, you have to turn off DEP and PIE (ASLR). See compilation instructions below.

Look, ma! No loops! Byte count is for the assembled opcodes of func + e + f. Works on 32 bit input. Sure, you'll eventually run out of stack space, but the number will overflow before then. Obviously, a loop would have been much smaller (and easier) to write.

How it works:

1. Copy payload code to stack-relative space (No modification of %rsp)
3. Payload calculates the Fibonacci number in %rax and self-unwinds without ever looping

### Full testing program:

// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
.global main

message: .asciz "%d"
main:
mov $N, %rdi call func mov %eax, %esi mov$message, %rdi
xor %eax, %eax
call printf
xor %eax, %eax
ret

func:
// We'll take %rdi, but we'll slice it to 32 bits
// %edi is arg, r8d is our counter.
mov %edi, %r8d
// Make 2 copies for arithmetic
mov %r8d, %eax
// Set up stack offset
// N * 32, need 64 bits to work with %rsp
imul $(eof - e), %eax neg %rax mov %rsp, %r9 lea (%rax, %r9), %r9 // Initialize for Fibonacci xor %ebx, %ebx xor %eax, %eax inc %eax // Copy initial payload: // Because PIE is turned off, we can use 32-bit addressing for local // Stack still seems to be in 64-land, however mov$e, %esi
mov %r9, %rdi
mov $(eof - e), %ecx rep movsb // Go to stack offset jmp *%r9 e: // The payload: dec %r8d jg f ret f: // Do actual Fibonacci stuff lea (%ebx, %eax), %edx mov %eax, %ebx mov %edx, %eax // Self-replicate mov %r9, %rsi mov$(eof - e), %cl
rep movsb
eof:


I decided on 32-bit input because the stack is not all valid for 64 bits, so we'd run out anyway. It overflows after a we get high enough input, but that's expected.

### Compilation:

# Prints 55
# Replace 10 with the input number (1-indexed):
gcc -no-pie -z execstack execstack_fibonacci.sx -DN=10 -g

• The -z execstack tells the linker to turn off DEP for this program. (Allow the stack to be executable)
• The -no-pie turns off ASLR.
• The -DN10 is just easy input control.
• The -g is for debugging control. Turn it off if you want.

Note: this will NOT work in MinGW because the DEP policy is managed by the OS on Windows. In fact, -z isn't even recognized by MinGW's ld.

### Hex dump:

funcs='func e f'
for el in $funcs; do echo 'Dump$el'
gdb -batch -ex "disas/r $el" ./a.out | sed '/^$/d'
done
gdb -batch -ex "print eof - e" ./a.out

• You may be able to save quite a few bytes here, as there are a lot of unnecessary REX prefixes, and there isn't nearly enough push/pop abuse. Commented Jan 16, 2021 at 14:56

# Javascript, 24 bytes - recursive version, 33 bytes - usage of Binet's formula, 46 bytes - continuous approximation with the "phi" itself

Usage of "Binet's formula" and a bitwise "OR" operator to round the result. Originally in the "Binet's formula" you have to subtract the so-called "smaller phi to the n-th power". "Smaller phi" (-0.618...) is inside the (-1;1) interval, so it gets closer to 0 with each positive power - that's why we can leave it, and just round the meaningful part. Function itself is an anonymous one, declared with the arrow function declaration.

n=>(((5**.5/2+.5)**n)/5**.5)+.5|0


Try it online!

Recursive version - arrow function declaration. Check whether n is less than 3, if so return 1, else do it again (at least) 2 more times, but with an argument of value n-1 and n-2:

f=n=>n<3?1:f(n-1)+f(n-2)


Try it online!

Continuous approximation. Ni * phi = Ni+1.

WARNING - RUNNING THIS CODE WILL END UP AS AN INFINITE AMOUNT OF ALERTS (next after clicking "ok")

f=n=>{l=n/2+5**.5/2*n+.5|0;alert(l);f(l)};f(1)

# V (vim), 32 bytes

i1
1<esc>qqkyjGp:s:\n:+
C<C-r>=<C-r>"
<esc>@qq@q


(don't)Try it online!

Prints the sequence forever.

Output is not visible on TIO, so here's the first 99 iterations: Try it online!

Last accurate value is $$\7540113804746346429\$$ after which it exceeds the integer limit.

# Duocentehexaquinquagesimal, 5 bytes

±∊YO$ Try it online! Link is to a version with output; this one just writes the sequence to memory. Outputs codepoints of the entire sequence. Stops eventually because of memory limitations. # Branch, 18 bytes 1XY[/x#^\yX^+Y10.]  Try it on the online Branch interpreter! Outputs infinitely. Eventually starts producing garbage values because long long int overflows but that seems to be acceptable. ## Explanation 1 Set the node's value to 1 XY Set the X and Y registers to 1 [ ] While value is not 0 (this will always be true in this program) /x# Move to the left child, set to the X register, and output as number ^\ Move to the parent and then right child (go to right sibling) yX Set to the Y register, then set the X register to that value ^+Y Move to root, sum the children (X + Y), and set the Y register 10. Place 10 and output as character; this also keeps the loop going  # C (clang), 797047 46 bytes y;z;main(x){for(;printf("%i ",z=x+y);y=z)x=y;}  Try it online! Uses a for-loop instead of a while-loop just because I use it more and doing while() gives the same byte count. Thanks to ceilingcat for golfing 9 bytes. Thanks to Jo King for golfing 23 bytes. Thanks to ceilingcat for golfing another byte. • 42 bytes – c-- Commented Jul 21, 2022 at 18:00 # Knight, 20 19 bytes ;=x=y 1W!Ox=y+x=x y  Try it online! -1 byte: W1;Ox -> W!Ox The "print infinitely" variant. (It will eventually overflow). It is a simple add and swap loop. Ungolfed: # init x and y to 1 ; = x (= y 1) # loop forever # since OUTPUT evaluates to NULL, we # can just invert the condition : WHILE !(OUTPUT x) { # Add and swap : = y + x (= x y) }  # Python 3, 46 44 bytes lambda n,a=5**.5:((.5+a/2)**n-(.5-a/2)**n)/a  Try it online! Uses Binet's formula to derive the nth Fibonacci number. Very wrong answer from me misreading the question: g=lambda n:n+g(n-1)if n else n  Try it online! • The logic is right, but it does start to drift pretty quickly due to floating point errors. I'm not sure if this is 100% Kosher. Commented Oct 7, 2021 at 11:26 • Fair. It's probably fine but it was not specified, so I guess we're in the dark. Commented Oct 7, 2021 at 11:32 # Mascarpone, 45 bytes v['1.]v*'b<^[v{^vv'b>'a<[ab]v*'b<^a' .:!]v*:!  Try it online! Outputs the numbers in unary, separated by newlines. High-level explanation (go read the language specification first): I redefine the interpreter to have two symbols, a and b, which kind of act as variables. Each symbol's operation prints a certain amount of 1s, so they kind of act as numbers in unary, and the operation corresponding to the string ab prints out the sum of a and b. At the start, a corresponds to 0 and b is 1. Each step, I simultaneously redefine (a, b) = (b, a+b) and then I output the new value of a. Slightly less high-level explanation: I will replace the newline with N because its only function is to help push a newline character — it doesn’t actually do anything special in terms of the logic of the program. Due to the longness of the program, I’ll divide this explanation up into parts. The beginning: v['1.]v*'b<^  This changes the current interpreter so that the symbol b corresponds to the operation of outputting a single 1. (a corresponds to a no-op by default, so it doesn’t have to be mentioned here). The rest of the program: I will use the notation [x] (where x can be any character) to mean “the operation the current interpreter associates with the symbol x’, since that’s a lot to type and I don’t have much margin space to write the explanation in. [v{^vv'b>'a<[ab]v*'b<^a'N.:!]v*:! [ :!]v*:! Loop forever: v{^ Hard to explain v Create a new interp, 'a< where a is assoc with v'b> [b] 'b< and b is assoc with [ab]v* [ab] (i.e. [a], then [b]) ^ Set current interp := that interp a Now run the op corresponding to a 'N. and print a trailing newline.  # flax, 3 bytes 1+ⁿ  Port of the Jelly answer. Takes input from stdin. Works similarly to the Jelly answer. # Desmos, 33 31 bytes b=.5 f(n)=round((b+b5^b)^n/5^b)  Try It On Desmos! f(n) = 1,1,2,3,5,... for n=1,2,3,4,5,... • 29 bytes using a regression. Commented Jul 27, 2022 at 1:06 ## RASEL, 12 bytes. 1:.:3\01\--#  ## Regex 🐇 (ECMAScriptRME / Perl / PCRE / Raku), 8 bytes ^(xx?)*$


Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2
Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33
Attempt This Online! - PCRE2 v10.40+
Try it online! - Raku

This uses the same technique as my Perl answer – it counts how many distinct partitions $$\n\$$ has as a sum of the numbers $$\1\$$ and $$\2\$$. But the focus here is on variations possible in the regex, treating the logic behind invoking it as a black box – as the language this answer is written in.

That block box doesn't just count the number of overlapping substrings that match (which would just be 1 with this regex, since it's anchored on both sides) but the number of ways in which different choices can lead to a full match (where choices are available, that is – in atomic constructs, the element of choice is eliminated). The counting of this is implemented by forcing the regex engine to backtrack at the end of any complete successful match (by turning it into a failed match), incrementing a counter every time that is done.

One interesting way to modify the Fibonacci sequence regex is to change its indexing. Getting the sequence to start one earlier, yielding $$\0, 1, 1, 2, 3, 5, 8...\$$, is trivial, but the others are interesting, and starting 4 later is where it begins to get difficult (and I'm sure it can be golfed better than I have so far). At certain point, it should become optimal to emulate (xx?)* in the extra space that is missing, but I haven't worked out how to do that yet.

2 earlier - 13 bytes - Try it online!: ^xx(xx?)*$|^$
1 earlier  -  9 bytes - Try it online!: ^x(xx?)*$ original - 8 bytes - Try it online!: ^(xx?)*$
1 later  -  10 bytes - Try it online!: ^x?(xx?)*$ 2 later - 16 bytes - Try it online!: ^x?x?(xx?)*(^|)$
3 later  -  22 bytes - Try it online!: ^x?x?x?(xx?)*(^|^x?|)$ 4 later - 55 bytes - Try it online!: ^(?(?=xxx)(x?){4}(xx?)*|(|(x()?)?x$|(x\B)?x?(|$)?)?x*)$`

To go 3 earlier or beyond, the rules would need to be extended to allow returning a negative sign via a capture group being set or unset (because there can't be a negative number of choices).