Try it online!
0-based, so input n gives the first n+1 results.
Uses the recursion from OEIS:
a(n) = a(n-1) + 2*a(n-2) + 1
Let's go through the program:
This is a constant stage: it discards the input and sets the working string to
0, the initial value of the sequence. The
) wraps this stage in a group. That group itself does nothing, but almost every stage (including group stages) records its result in a log, and we'll need two copies of the
0 on that log for the program to work.
There's a bunch of configuration here:
"$+"+ wraps the stage in a loop. The
"$+" is treated as a substitution, and
$+ refers to the program's input, i.e. n. This means that the loop is run n times.
¶< wraps each iteration in an output stage, which prints the stage's input with a trailing linefeed (so the first iteration prints the zero, the second iteration prints the first iteration's result and so on).
The stage itself replaces the entire working string with the substitution on the last line. That one makes use of an implicit closing parenthesis and implicit arguments for the repetition operator
*, so it's actually short for:
The stuff inside the parentheses can be broken up into three parts:
$&*_: gives a string of a(n-1)
_: gives a single
2*$-1*_: gives a string of 2*a(n-1)
$-1 refers to the penultimate result in the result log, i.e. the loop iteration before the last. That's why we needed to copies of the zero on the log to begin with, otherwise this would refer to the program's input on the first iteration.
$.(…) measures the length of the resulting string. In other words, we've computed
a(n) = a(n-1) + 1 + 2*a(n-2) by going through unary (not really though:
$.(…) is lazy and doesn't actually evaluate its content if it can determine the resulting length directly through arithmetic, so this is even quite efficient).
The result of the final loop iteration (the n+1th element of the sequence) is printed due to Retina's implicit output at the end of the program.