[Question]
  [
Recamán's sequence ([A005132](http://oeis.org/A005132)) is a mathematical sequence, defined as such:
```
A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n
```
A pretty LaTex version of the above (might be more readable):
$$A(n) = \begin{cases}0 & \textrm{if } n = 0 \\
A(n-1) - n & \textrm{if } A(n-1) - n \textrm{ is positive and not already in the sequence} \\
% Seems more readable than
%A(n-1) - n & \textrm{if } A(n-1) > n \wedge \not\exists m < n: A(m) = A(n-1)-n \\
A(n-1) + n & \textrm{otherwise}
\end{cases}$$
The first few terms are `0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11`
To clarify, `is new` means whether the number is already in the sequence.
Given an integer `n`, via function argument or STDIN, return the first `n` terms of the Recamán sequence.
---
This is a code-golf challenge, so **shortest code wins.**
  
[Answer]
# CJam, ~~34~~ 33 bytes
```
0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`
```
[Try it online.](http://cjam.aditsu.net/)
### Example run
```
$ cjam <(echo '0ali{_W=_I-__0<4$@#)|@I+@?+}fI1>`') <<< 33
[0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42 17 43 16 44 15 45 14 46]
```
### How it works
```
0ali                               " Push S := [ 0 ] and read an integer N from STDIN.    ";
    {                      }fI     " For each I in [ 0 ... (N - 1) ]:                     ";
     _W=                           "   X := S[-1].                                        ";
        _I-                        "   Y := X - I                                         ";
            _0<                    "   A := (Y < 0)                                       ";
           _   4$@#)               "   B := (Y ∊ S)                                       ";
                     @I+           "   Z := X + I                                         ";
                    |   @?         "   C := (A || B) ? Z : Y                              ";
                          +        "   S += [C]                                           ";
                              1>`  " Push str(S[1:]).                                     ";
```
[Answer]
# Hexagony, 212 bytes
```
?\..$@.=.'">'_<>}/..&\_.._!\.\].\"&"&=(<_...>\[.+.<_$|_...{.|.....}'.../<..|&.....'/..".>$/{.<\.\$\>\._?...><?$$.\[._\_}$&..~.|"$\./..{&_$....$'.|_...$}|_.-..;_....'}".'...2.....$?&....3..=.<_.....?.-+{......}\</$.}
```
[Try it online!](https://tio.run/##JY5NCgIxDIXPYgmtIH4DCm7stN7DSHAhutKtMlOvPrY1i4QX3t/j9r7eX8/PsmQFOTESXAoWUxnAq4GtlAvqvPPjOtYH6cyGaDI3MDHTpoS6hgiz7zhUvSPJMBEVFU2K5aaOWYQzplakcr/MTpRKn7xJk0qgW0upZwtH64bF0TJ23V5yj9lTG/dSkNluJv5lNA5CWZbDDw)
**Input:** a single, positive integer \$n\$ on `stdin`.
**Output:** all terms of Recaman's sequence up to and including \$A(n)\$, separated by spaces (note that this means the program will print a total of \$n + 1\$ terms).
# Expanded
[![expanded](https://i.stack.imgur.com/blpJp.png)](https://i.stack.imgur.com/blpJp.png)
# Explanation
Apologies if this is confusing, but it's my first time with Hexagony, so rest assured that it confuses me too.
Let \$n = 6\$.
The instruction pointer (IP) starts out in the NW corner, moving along the black path.
`?` reads \$n\$ from `stdin` and stores it in the current memory edge.
Next, we copy \$n\$ three times while backing up the memory pointer.
We also flip the memory pointer and decrement the edge it points to.
```
"&"&"&=(
```
The IP eventually wraps around to the upper left corner again, jumping over `\` and looping through the rest of the black path.
This loop continues until the current edge is 0, at which point the graph looks like so:
[![initialized](https://i.stack.imgur.com/EhxL7.png)](https://i.stack.imgur.com/EhxL7.png)
This forms the skeleton of our memory layout.
Each `vertical` edge now stores a value \$i\$ from 0 to 6; later, these same edges will store the terms \$A(i)\$ of the sequence as they are computed.
Each `vertical` edge also has 4 contiguous edges that are used for later computations. Let's explain them now:
* `head` is used for several purposes, but never to store anything permanently because it is frequently overwritten by other operations.
* `tail` is generally used as a temporary variable, but it remains 0 for the last \$i\$ in the sequence, telling the program when to stop.
* `prev` stores the value of \$A(i - 1)\$
* `copy` straightforwardly stores a copy of \$i\$ or, later, \$A(i)\$
Once the program is done initializing its memory graph, it branches off the black path and onto the red path near the NE corner.
First, `!` prints the decimal representation of `vertical` to `stdout`.
Next, we move the memory pointer to `tail` and test for zero:
```
'<
```
If it is zero, `@` terminates the program immediately; otherwise, we move to `head` and set it to 32 (an ASCII space):
```
}=}?32
```
[![space](https://i.stack.imgur.com/WVgxC.png)](https://i.stack.imgur.com/WVgxC.png)
`;` then prints this space to `stdout`.
Finally, we copy `vertical` to the next `prev`:
```
"?&"&
```
[![cvp](https://i.stack.imgur.com/Bn2Jp.png)](https://i.stack.imgur.com/Bn2Jp.png)
Now that the memory pointer is on the next term, we copy this term's `vertical` to *its* `copy` before moving to *its* `vertical`:
```
'&{=
```
[![cvc](https://i.stack.imgur.com/pNolo.png)](https://i.stack.imgur.com/pNolo.png)
`-` computes `prev` - `copy`, which is really \$A(i - 1) - i\$, and stores it in `vertical`:
[![subtraction](https://i.stack.imgur.com/Kr92R.png)](https://i.stack.imgur.com/Kr92R.png)
If `vertical` is not positive, `<` deflects the IP onto the green path, where `+` instead computes `prev` + `copy` (\$A(i - 1) + i\$) and stores it in `vertical`:
[![addition](https://i.stack.imgur.com/x0oiu.png)](https://i.stack.imgur.com/x0oiu.png)
The IP then wraps around to the SW corner, eventually returning to the beginning of the red path and starting the cycle over again.
However, if `vertical` is positive, we have to make sure it doesn't already exist in the sequence before printing it.
In this case, the `<` in the SE corner branches to the SE, wrapping around and staying on the red path.
First, we copy `vertical` to `head`:
```
"?&
```
This puts the memory pointer in a position so that successive loops can enter at the next `|` mirror.
Next, we copy `head` to the previous term's `tail` and move to *its* `head`.
```
"?&'
```
`-` computes `vertical` - `tail` (\$A(i - 1) - A(i)\$) and stores it in `head`.
Hexagony treats zero as a negative number, so we have to do some convoluted branching to test if `head` is exactly zero.
All that's necessary to know is that if `head` is zero, we've found a duplicate term, and the program will branch onto the yellow path.
Otherwise, it will return to the red path at the `{` instruction.
If `head` is zero, we return to the latest term of the sequence with `[`, which executes the subroutine along the pink and blue paths, before `+` computes \$A(i - 1) + i\$) like above.
We then return to the red path.
If `head` is not zero, we check if the current term is zero:
```
{<
```
If it is, we call the subroutine and go back to the red path through a convoluted series of mirrors.
If it isn't, we move to compare the next term, returning to the aforementioned `|` mirror.
---
Images created using Timwi's [Hexagony Colorer](https://github.com/Timwi/HexagonyColorer) and [Esoteric IDE](https://github.com/Timwi/EsotericIDE).
[Answer]
## Ruby, ~~71~~ 70 bytes
```
f=->n{a=[0];(n-1).times{|i|a+=[[b=a[-1]-i-1]-a!=[]&&b>0?b:b+2*i+2]};a}
```
A very "word-for-word" implementation of the definition.
[Answer]
# Haskell, 74
```
l=0:0#1
a§v|a<0||a`elem`r v=v|1<2=0-v
a#b=a+(a-b)§b:l!!b#(b+1)
r=(`take`l)
```
Example usage:
```
λ> r 20
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62]
```
[Answer]
## Python 2, ~~78~~ ~~75~~ ~~73~~ 69 Bytes
Kudos to xnor and flornquake  
Now almost 10 bytes shorter than the initial answer
```
m=p,=0,
exec"p+=1;k=m[-1]-p;m+=k+2*p*(k*(k>0)in m),;"*input()
print m
```
[Answer]
# Golfscript (41 ~~45~~)
Try it [online here](http://golfscript.apphb.com/?c=OzEwMAooLDEsXHs6fjEkPX4pLTpeMTxcLl4%2FKSEhQHxeXHt%2BKTIqK30qK30vYA%3D%3D):
```
(,1,\{:~1$=~)-:^1<\.^?)!!@|^\{~)2*+}*+}/
```
## Explanation
This is for the original 45 bytes solution, but it's still pretty much the same:
```
(,              # push array [0 .. n-1]
[0]\            # push sequence elements as [0] and reverse stack
{               # foreach element in [0 .. n-1] do:
  :m;           # store current element in m and discard
  .m=           # get the previous sequence element
  m)-:^         # subtract the current index from it and store in ^
  0>            # is that number greater than 0?
  \.^?)!        # is that number new to our sequence?
  @&            # logically and both checks
  {^}           # if true, push ^
  {^m)2*+}      # otherwise, add the index twice and push
  if
  +             # add new element to our sequence
}/
`               # make output pretty
```
*Edit #1:* Thanks to Dennis for shaving off 4 bytes.
[Answer]
# [dc](https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html), 46 bytes
```
sn[z+z+d0r:a]sF0[pz-d1>Fd;a0<Fddd:azln!<M]dsMx
```
[Try it online!](https://tio.run/##S0n@b2rwvzgvukq7SjvFoMgqMbbYzSC6oEo3xdDOLcU60cDGLSUlxSqxKidP0cY3NqXYt@L/fwA "dc – Try It Online")
This program takes input from an otherwise empty stack and outputs to stdout (newline delimited).
I'm really proud of this one - it's beating everything that isn't a dedicated golfing language, and showcases three of my favorite dc golfing tricks:
* Stack size used as an index variable
* Refactoring "if A then B else C" into "unconditionally C, and if A then D" where C and D combine to make B
* the little-used random access array feature to solve a uniqueness constraint
# Explanation
```
sn             Stores the input in register n
[z+z+0r:a]sF   Defines the macro F, which: 
    z+z+         adds twice the stack size/index variable
    0r:a         resets the "uniqueness" flag to 0 in the array a
               In context, F is the "D" in my description above, 
               changing A(z-1)-z to A(z-1)+z
0              The main loop starts with the previous sequence member on top of 
               the stack and total stack depth equal to the next index. 
               Pushing a zero accomplishes both of these things.
[              Start of the main loop M
  p               Print the previous sequence member, with newline (no pop)
  z-             Calculate A(z-1)-z
  d1>F           If that's nonpositive, (F)ix it to be A(z-1)+z
  d;a            a is my array of flags to see if we've hit this value before
  0<F            If we have, (F)ix it! (nonzero = flag, since ;a is zero by
                 default, and also zero if we just (F)ixed and therefore 
                 don't care about uniqueness right now)
  ddd            Make one copy to keep and two to eat
  :a             Flag this entry as "used" in the uniqueness array a
  zln!<M         If our "index variable" is n or less, repeat!
]dsMx          End of main loop - store it and execute
```
[Answer]
## JavaScript -  ~~81 80 79~~ 70
Kudos to edc65 for helping me save 9 bytes
```
f=n=>{for(a=[x=i=0];++i<n;)a[i]=x+=x>i&a.indexOf(x-i)<0?-i:i;return a}
```
[Answer]
## JavaScript, ES6, ~~74~~ 69 characters
Run the below code in latest Firefox's Web Console.
```
G=n=>(i=>{for(r=[t=0];++i<n;)r[i]=t+=i>t|~r.indexOf(t-i)?i:-i})(0)||r
```
Will try to golf it more later.
Example usage:
```
G(11) -> 0,1,3,6,2,7,13,20,12,21,11
```
[Answer]
# MATLAB, ~~83~~ 78 Bytes
Save the below as `f.m` (73 Bytes)
```
A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end
```
Run from command window (5 bytes)
```
n=9;f
```
If the above is not legal, then it requires 90 bytes.
```
function A=f(n) 
A=0;for i=1:n-1 b=A(i)-i;A(i+1)=b+2*i;if b>0&&~any(A==b) A(i+1)=b;end;end
```
[Answer]
# R: 96 characters
Golfed:
```
A=function(s,n,m,i){if(m==n){return(s)}else{t=i-m;if(t%in%s||t<0){t=i+m};s=c(s,t);A(s,n,m+1,t)}}
```
Ungolfed:
```
A = function(s,n,m,i) {
    if(m==n){return(s)}
    else{
        t=i-m
        if(t%in%s||t<0){t=i+m}
        s=c(s,t)
        A(s,n,m+1,t)
    }
}
```
Sample Run:
```
> An(0,34,1)
[1]   0   1   3   6   2   7  13  20  12  21  11  22  10  23   9  24   8
[18]  25  43  62  42  63  41  18  42  17  43  16  44  15  45  14  46  79
```
[Answer]
# JavaScript, 63 bytes
```
n=>(g=y=>n-x?g(a[++x]=a.includes(z=y-x)|z<0?+y+x:z):a)(a=[x=0])
```
[Try it online](https://tio.run/##BcFtCoMwDADQ6yR0DTLYH1mUnUNlBr@ouFR0G23Z3bv3VvnKORxuf1v145RnzsoVLBy5UhvqBaQxJnQs5HTYPuN0QuJoA/7SvahNNKFMWAqCcBO46DAPXk@/TbT5BRoiehyHRLjesKOX7ADPi0OuZnCItHqnfas95j8)
[Answer]
# [Perl 6](http://perl6.org/), ~~62~~ 57 bytes
~~{(0,{$*-@*+@*\*2\*($*!>@*||$*-@*∈@*)given @*[\*-1]}...\*)[^$*]}~~
```
{(0,{($!=@_[*-1])+@_-@_*2*($!>@_&&$!-@_∉@_)}...*)[^$_]}
```
*-5 bytes thanks to Jo King*
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/WsNAp1pDRdHWIT5aS9cwVlPbIV7XIV7LSAsoaOcQr6amogjkP@rodIjXrNXT09PSjI5TiY@t/V@cWKmQpmFqoPkfAA "Perl 6 – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 19 bytes
```
¾ˆG¯¤N-DŠD0›*åN·*+ˆ
```
[Try it online!](https://tio.run/##ASkA1v8wNWFiMWX//8K@y4ZHwq/CpE4tRMWgRDDigLoqw6VOwrcqK8uG//81MA "05AB1E – Try It Online")
**Explanation**
```
¾ˆ                    # Initialize the global list with 0
  G                   # for N in [1, input-1] do:
   ¯                  # push the global list
    ¤N-               # subtract N from the last item in the list
       D              # duplicate
        Š             # move the copy down 2 spots on the stack
         D            # duplicate again
          0›          # check if it is positive
            *         # multiply, turning negative results to zero
             å        # is the result already present in the list?
              N·*     # multiply by N*2
                 +    # add to the result
                  ˆ   # add this to the list
```
[Answer]
# [K (oK)](https://github.com/JohnEarnest/ok), 53 bytes
**Solution:**
```
{$[y>c:#x;o[x,(r;*|x+c)(r in x)|0>r:*|x-c;y];x]}[,0;]
```
[Try it online!](https://tio.run/##y9bNz/7/v1olutIu2Uq5wjo/ukJHo8haq6ZCO1lTo0ghM0@hQrPGwK7ICiikm2xdGWtdEVsbrWNgbWgY@/8/AA "K (oK) – Try It Online")
**Explanation:**
Recursive solution.
```
{$[y>c:#x;o[x,(r;*|x+c)(r in x)|0>r:*|x-c;y];x]}[,0;] / the solution
{                                              }[,0;] / lambda with first arg set as list containing 0
 $[      ;                                  ; ]       / if[condition;true;false]
       #x                                             / length of x
     c:                                               / save as c
   y>                                                 / y greater than? (ie have we produced enough results?)
                                             x        / return x if we are done
          o[                             ;y]          / recurse with new x and existing y
                                      x-c             / subtract c from x
                                    *|                / reverse first, aka last
                                  r:                  / save result as r
                                0>                    / 0 greater than?
                               |                      / or
                       (      )                       / do together
                        r in x                        / r in x?
              ( ;     )                               / use result to index into this 2-item list
                   x+c                                / add c to x
                 *|                                   / reverse first, aka last 
               r                                      / result
            x,                                        / append to x
```
[Answer]
# [J](http://jsoftware.com/), 36 bytes
```
(,][`(+2*#)@.(e.+.0>[)~{:-#)^:(]`0:)
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NXRioxM0tI20lDUd9DRS9bT1DOyiNeuqrXSVNeOsNGITDKw0/2typSZn5CukKRga/AcA "J – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 65 bytes
```
n=a=0
v=[]
exec'a+=[n,-n][a+n in v];print a;n-=1;v+=a,n;'*input()
```
[Try it online!](https://tio.run/##BcFBCoAgEAXQvadwZ6WCtpU5ibgYQsjNT8KkTj@9179xXthFQExBTcpF1bcehi1lOI@S2UI36FlSvxuG5gRPMU1L7JDM1tCfsawiMfw "Python 2 – Try It Online")
Avoids negative numbers by adding them to the list of already visited numbers.
[Answer]
## Java, 144
```
int[]f(int n){int[]a=new int[n];a[0]=0;int i,j,k,m;for(i=0;i<n-1;){k=a[i++]-i;m=0;for(j=0;j<i;)if(k==a[j++])m=1;a[i]=m<1&k>0?k:k+2*i;}return a;}
```
[Answer]
### Powershell (103)
```
$n=Read-Host;$a=@(0);$n-=1;1..$n|%{$x=$a[-1]-$_;if($x-gt0-and!($a-like$x)){$a+=$x}else{$a+=$x+2*$_}};$a
```
Another 'word-for-word' implementation down here as well. Surprisingly readable for PowerShell, too.
Sequence is stored in the array $a, and printed out one term per line.
For $n=20 if we run the statement `$a-join","` we get
```
0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62
```
[Answer]
## Lua - ~~141 135 139~~ 135
```
function s(n)a,b={1},{[0]=0}for i=1,n do k=b[i-1]-i c=k+i+i if(k>0)and(a[k]==nil)then b[i],a[k]=k,1 else b[i],a[c]=c,1 end end return b end
```
readable version:
```
function s(n)
a,b={1},{[0]=0}
for i=1,n do 
   k=b[i-1]-i 
   c=k+i+i
   if (k>0) and (a[k]==nil) then 
      b[i],a[k]=k,1 
   else 
      b[i],a[c]=c,1
   end 
end 
return b 
end
```
I use 2 tables, the first one is called *a* and it is built so that a[i]=1 iff *i* has already appeared in the sequence, *nil* otherwise, while the second table actually holds the sequence
[Answer]
## Python, 73
```
def f(x,t=0):
 if x:t=f(x-1);t+=2*x*(t*(t>0)in map(f,range(x)))
 return t
```
Edit 1: Thanks to @xnor's tips on the other Python answer!
(I just realised that both look very similar.)
Edit 2: Thanks again, @xnor.
[Answer]
## Groovy : 122 118 111 chars
Golfed:
```
m=args[0] as int
a=[0]
(1..m-1).each{n->b=a[n-1];x=b-n;(x>0&!(x in a))?a[n]=x:(a[n]=b+n)}
a.each{print "$it "}
```
Ungolfed:
```
m = args[0] as int
a = [0]
(1..m-1).each { n->
    b = a[n-1]
    x = b-n
    ( x>0 & !(x in a) ) ? a[n] = x : (a[n] = b+n) 
}
a.each{print "$it "}
```
Sample Run:
```
bash$ groovy Rec.groovy 14
0 1 3 6 2 7 13 20 12 21 11 22 10 23
```
[Answer]
## Clojure : 174 chars
Golfed:
```
(defn f[m a](let[n(count a)b(last a)x(- b n)y(if(and(> x 0)(not(.contains a x)))x(+ b n))](if(= m n)a(f m(conj a y)))))(println(f(read-string(first *command-line-args*))[0]))
```
Ungolfed:
```
(defn f[m a]
  (let [n (count a) 
        b (last a) 
        x (- b n) 
        y (if (and (> x 0) (not (.contains a x))) x (+ b n)) ]
    (if (= m n) a (f m (conj a y))) ) )
(println (f (read-string (first *command-line-args*)) [0]) )
```
Sample run:
```
bash$ java -jar clojure-1.6.0.jar rec.clj 14 
[0 1 3 6 2 7 13 20 12 21 11 22 10 23]
```
[Answer]
# Mathcad, 54 "bytes"
[![enter image description here](https://i.stack.imgur.com/bY9ZM.jpg)](https://i.stack.imgur.com/bY9ZM.jpg)
---
From user perspective, Mathcad is effectively a 2D whiteboard, with expressions evaluated from left-to-right,top-to-bottom. Mathcad does not support a conventional "text" input, but instead makes use of a combination of text and special keys / toolbar / menu items to insert an expression, text, plot or component. For example, type ":" to enter the definition operator (shown on screen as ":=") or "ctl-shft-#" to enter the for loop operator (inclusive of placeholders for the iteration variable, iteration values and one body expression). What you see in the image above is exactly what appears on the user interface and as "typed" in.
For golfing purposes, the "byte" count is the equivalent number of keyboard operations required to enter an expression.
[Answer]
# [PHP](https://php.net/), 89 bytes
```
$f=function($n){for(;$i<$n;$s[$r[$i++]=$p=$m]=1)if($s[$m=$p-$i]|0>$m)$m=$p+$i;return$r;};
```
[Try it online!](https://tio.run/##HcjLCsIwEEbhV@nih86QCnXlYhp9kJJVTeiAuRDblfrssbo5cL6yljbdylEEG/a0bJoTIfEr5EoCnZAEzxl1hhrjLIpFdPbMGujn8ZAT1L3HKyL/10Cl@m2vCVU@0vyy5k5jeeS7p37ohw6BLiOztC8 "PHP – Try It Online")
Ungolfed:
```
$f = function ($n) {
    for (; $i < $n; $s[$r[$i++] = $p = $m] = 1) {
        if ($s[$m = $p - $i] | 0 > $m) {
            $m = $p + $i;
        }
    }
    return $r;
};
```
* `$r` for my result
* `$s` for tracking seens
* `$p` previous value
* `$m` *m*ext value
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~116 111~~ 109 bytes
```
*f(n){int*a=calloc(4,n),i=0,j,k,m;for(;~i+n;a[i]=k+(m|k<1)*2*i)for(k=a[i++]-i,m=0,j=i;j--;)m=k-a[j]?m:1;n=a;}
```
[Try it online!](https://tio.run/##JY7NDoIwEITvPsVKYtLfBIgnl8YHIRyaGsxSWwjiCfHVsdXTZL7Z2V2n787tu@hZ5CvFRVjj7OMxOnZWkSsypRqUVwH7cWb4IRnRttQZL1l4@6biohbEc@hNCqTsNKmQW4Zw0Bp5MF7bduiu4VJhNBa3Pd2BYCkyvh4AshMWDPSsqoFjQnnfj1PCJSZpoKqTSgkccglgmtNAz6BQp1shj6QgP/bvbzC9licriuS2/Qs "C (gcc) – Try It Online")
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 19 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
É╖C8½ΔL▄░▬L+≡ΩSa⌂¼╧
```
[Run and debug it](https://staxlang.xyz/#p=90b74338abff4cdcb0164c2bf0ea53617faccf&i=3%0A100&a=1&m=2)
Unpacked, ungolfed, and commented, it looks like this. It keeps the sequence so far on the stack, and remembers `A(n - 1)` in the X register. The iteration index is used for `n`. The first time through, it's 0, but in that iteration it generates the 0 without any special cases, so there's no need to adjust for the off-by-1 index.
```
0X      push 0 to main stack and store it in X register, which will store A(n - 1)
z       push an empty array that will be used to store the sequence
,D      pop input from input stack, execute the rest of the program that many times
  xi-Y  push (x-register - iteration-index) and store it in the Y register
        this is (A(n - 1) - n)
  0>    test if (A(n - 1) - n) is greater than 0 (a)
  ny#   count number of times (A(n - 1) - n) occurs in the sequence so far (b)
  >     test if (a) > (b)
    y   (A(n - 1) - n)
    xi+ A(n - 1) + n
  ?     if/else;  choose between the two values based on the condition
  X     store the result in the X register
  Q     print without popping
  +     append to sequence array
```
[Run and debug this one](https://staxlang.xyz/#c=0X+++++%09push+0+to+main+stack+and+store+it+in+X+register,+which+will+store+A%28n+-+1%29%0Az++++++%09push+an+empty+array+that+will+be+used+to+store+the+sequence%0A,D+++++%09pop+input+from+input+stack,+execute+the+rest+of+the+program+that+many+times%0A++xi-Y+%09push+%28x-register+-+iteration-index%29+and+store+it+in+the+Y+register%0A+++++++%09this+is+%28A%28n+-+1%29+-+n%29%0A++0%3E+++%09test+if+%28A%28n+-+1%29+-+n%29+is+greater+than+0+%28a%29%0A++ny%23++%09count+number+of+times+%28A%28n+-+1%29+-+n%29+occurs+in+the+sequence+so+far+%28b%29%0A++%3E++++%09test+if+%28a%29+%3E+%28b%29%0A++++y++%09%28A%28n+-+1%29+-+n%29%0A++++xi%2B%09A%28n+-+1%29+%2B+n%0A++%3F++++%09if%2Felse%3B++choose+between+the+two+values+based+on+the+condition%0A++X++++%09store+the+result+in+the+X+register%0A++Q++++%09print+without+popping%0A++%2B++++%09append+to+sequence+array&i=3%0A100&a=1&m=2)
[Answer]
## Pyth, 31 bytes
```
VQ=+Y?Y?|>NeYhxY-eYN+eYN-eYNZ)Y
```
[Answer]
# x86 machine code, 29 bytes
```
00000034: 89 fe 31 c0 99 eb 11 29 d0 78 0a 60 89 f7 89 d1  ..1....).x.`....
00000044: f2 af 61 75 03 8d 04 50 ab 42 e2 eb c3           ..au...P.B...
```
Commented assembly:
```
        .intel_syntax noprefix
        .globl recaman
        // input: ECX: n, EDI: u32[n]
        // output: stored to EDI
recaman:
        // Save the array pointer to ESI
        mov     esi, edi
        // EAX (A(n)) = 0
        xor     eax, eax
        // EDX (n) = 0
        cdq
        // Store first word
        jmp     .Lstore
.Lloop:
        // A(n - 1) - n
        sub     eax, edx
        // if negative, do A(n - 1) + n
        js      .Lneg_or_dup
.Lnot_neg_or_dup:
        // We need to save both EDI and ECX, so we do a lazy PUSHA/POPA.
        pusha
        // EDI = start of array
        mov     edi, esi
        // ECX = current output length
        mov     ecx, edx
        // Search for A(n - 1) - n
        repnz   scasd
        // restore registers
        popa
        // If the zero flag is set, we found a match.
        // If not, go directly to store
        jnz     .Lstore
.Lneg_or_dup:
        // Convert A(n - 1) - n to A(n - 1) + n by adding n * 2
        // EAX = EAX + EDX * 2
        lea     eax, [eax + 2 * edx]
.Lstore:
        // Store a u32 to EDI and autoincrement
        stosd
        // Increment length
        inc     edx
        // Decrement counter and loop if non zero
        loop    .Lloop
        // Return
        ret
```
[Try it online!](https://tio.run/##dVVtT9swEP6eX3HqtCmB8NIi7UMZSAiQVglpCDQNCaHI2E4alNiZ7ZQWxF9fd3bSJKbQD0lzb7577rkzraq9jNL1l1zQomYcflBtWC5Pg3cSYd6JVC6y0yDgS8OVgNH5KFjInIHilJREJJRxWoTodjRJDOwQpWLYfBVcZGYeHQdBkhBdJkl4MwrX0P720YwXiV4JQ5YgZKV4mi@DTp0V8rHYnNOJDw4wfFWbKVye301BxHB5MZtCfTS5Fw9DK1kbZ6aNVJyBkdYwaMNNh5a3ZMHBzDlg8mQFlbSJKedxO@sMS7lwb67zGDjLhxEuz@4gPAtFFMEJHHaapVSNC1nG9uG5XKCL8O0p@@vlZTOHNFfawLNUrNM9lVUD0ZUrLti/KqSsvJowGdiDcYSPHjtdPw7yYV4@eQqCZ8TkCx4Dk32A3UGAJ9325gptE6kSVld4upAm6QVeHn84hm3g1xbmR2nmthFABLMdjEFLeOb2RAIFeVnB9e/bn2cH17@uz/a7QFWt58RHb4bIaUOUabq23SZm26T9Np3foRetleLCtATZdqTb4NxyougcUuznh8AqXokXCzAlmg0dFXcdwneWaySV7kuSlVfRLHUUfOFKQlqQDHINmpvYgpPKGtEiUBJD5/vvvBD8GDIJLEdum2LloHa06LrmchvS5ZNmnUux4IjosEYbbsgFeFwBYbgnMhA74/dDcOKeu47dOzDp1AUnPfPu8Yk2E7RAnB@CNq/pNveJnet2dB1jSG1wOqniJXaw57WRPuyzjUm7gjod@rbs8Pp7wTf2FKG2w28Ps0Pl5kIK15e@GqtwgNp/w0A33NRqyAsTDNVuWcKzIlWFZ4S10NQup@iTpdcs18D7mnpD0TJ9WzYgvjcR91xXiP148vAx8Tf6772ekqJoivE3cdWA4J3VyQY5WRC6@ogxm43f7Pt1NLIXBK5cpHcuQnu5RMFr0HSruUdwwu/Hhw/HTljyEucidBfN4TJNcYPkL1ymVhJFjY1/OTnT8WGrs0Pc3VffljC14SN47WvAG8@k4egri2EUw7L1ewvegvU/amdTr/fKo8l/)
The input is a pointer to an `int32_t` array of `n` elements in `edi`, with `n` being in `ecx`.
The output will be stored into `edi`.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~56~~ 52 bytes
-2 bytes thanks to [Jo King](https://codegolf.stackexchange.com/users/76162/jo-king)!  
-2 bytes thanks to [dingledooper](https://codegolf.stackexchange.com/users/88546/dingledooper)!
```
->n{v,*d=0;n.times{|i|d<<v+=v<i||d!=d-[v-i]?i:-i};d}
```
[Try it online!](https://tio.run/##KypNqvyfZhvzX9cur7pMRyvF1sA6T68kMze1uLomsybFxqZM27bMJrOmJkXRNkU3ukw3M9Y@00o3s9Y6pfZ/gUJatKFh7H8A "Ruby – Try It Online")
**Commented**:
```
->n{ ... }                         # lambda function taking an integer
  v,*d=0                           # initialize list of sequence values d and previous value v
  n.times{|i| ... }                # run the following code for i = 0,1,...,n-1:
          v<i||d!=d-[v-i]?i:-i     #   i IF (v < i OR d != (d without v-i)) ELSE -i
       v+=                         #   add this to v
    d<<                            #   and append the new value of v to d
  d                                # return d
```
]