[Question]
  [
# Definition
1. a(1) = 1
2. a(2) = 1
3. a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2 where n is an integer
# Task
Given positive integer `n`, generate `a(n)`.
# Testcases
```
n  a(n)
1  1
2  1
3  2
4  3
5  3
6  4
7  5
8  5
9  6
10 6
11 6
12 8
13 8
14 8
15 10
16 9
17 10
18 11
19 11
20 12
```
# Reference
* Obligatory OEIS [A005185](http://oeis.org/A005185)
  
[Answer]
# Haskell, ~~35~~ 33 bytes
```
a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)
```
Defines a function `a`.
[Answer]
## [Retina](https://github.com/m-ender/retina), ~~84~~ ~~83~~ ~~79~~ 74 bytes
Byte count assumes ISO 8859-1 encoding.
```
.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1
```
[Try it online!](http://retina.tryitonline.net/#code=JShHYAouKwokKjsxwrYxwrYKK2A7KD89KDEpK8K2KDEpKykoPz0oPzwtMT4oMSspwrYpKykoPz0oPzwtMj4oMSspwrYpKykKJDMkNMK2CkczPWAKMQ&input=MQoyCjMKNAo1CjYKNwo4CjkKMTA) (The first line enables a linefeed-separated test suite.)
I'll have to golf this some more later.
[Answer]
# Julia, 29 bytes
```
!n=n<3||!(n-!~-n)+!(n-!~-~-n)
```
[Try it online!](http://julia.tryitonline.net/#code=IW49bjwzfHwhKG4tIX4tbikrIShuLSF-LX4tbikKCmZvciBuIGluIDE6MjAKICAgIEBwcmludGYoIiUydSAtPiAlMnVcbiIsIG4sICFuKQplbmQ&input=)
### How it works
We redefine the unary operator `!` for our purposes.
If **n** is **1** or **2**, `n<3` returns *true* and this is our return value.
If **n** larger than **2**, `n<3` returns *false* and the *||* branch gets executed. This is a straightforward implementation of the definition, where `~-n` yields **n - 1** and `~-~-n` yields **n - 2**.
[Answer]
# Sesos, 54 bytes
```
0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....
```
[Try it online](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKYWRkIDEKZndkIDEKYWRkIDEKZndkIDYKZ2V0CnN1YiAxCmptcAogICAgam1wCiAgICAgICAgc3ViIDEKICAgICAgICBmd2QgMQogICAgICAgIGFkZCAxCiAgICAgICAgcndkIDEKICAgIGpuegogICAgZndkIDEKICAgIHN1YiAxCiAgICByd2QgMgogICAgYWRkIDIKICAgIGptcAogICAgICAgIHJ3ZCA0CiAgICAgICAgam1wCiAgICAgICAgICAgIHN1YiAxCiAgICAgICAgICAgIGZ3ZCAzCiAgICAgICAgICAgIGFkZCAxCiAgICAgICAgICAgIHJ3ZCAzCiAgICAgICAgam56CiAgICAgICAgZndkIDQKICAgICAgICBqbXAKICAgICAgICAgICAgc3ViIDEKICAgICAgICAgICAgcndkIDMKICAgICAgICAgICAgYWRkIDEKICAgICAgICAgICAgcndkIDEKICAgICAgICAgICAgYWRkIDEKICAgICAgICAgICAgZndkIDQKICAgICAgICBqbnoKICAgICAgICByd2QgMwogICAgICAgIGptcAogICAgICAgICAgICBzdWIgMQogICAgICAgICAgICBmd2QgMwogICAgICAgICAgICBhZGQgMQogICAgICAgICAgICByd2QgMwogICAgICAgIGpuegogICAgICAgIGZ3ZCA0CiAgICAgICAgYWRkIDIKICAgICAgICBqbXAKICAgICAgICAgICAgcndkIDUKICAgICAgICAgICAgam1wCiAgICAgICAgICAgICAgICByd2QgMQogICAgICAgICAgICAgICAgam1wCiAgICAgICAgICAgICAgICAgICAgc3ViIDEKICAgICAgICAgICAgICAgICAgICBmd2QgMgogICAgICAgICAgICAgICAgICAgIGFkZCAxCiAgICAgICAgICAgICAgICAgICAgcndkIDIKICAgICAgICAgICAgICAgIGpuegogICAgICAgICAgICAgICAgZndkIDEKICAgICAgICAgICAgICAgIGptcAogICAgICAgICAgICAgICAgICAgIHN1YiAxCiAgICAgICAgICAgICAgICAgICAgcndkIDEKICAgICAgICAgICAgICAgICAgICBhZGQgMQogICAgICAgICAgICAgICAgICAgIGZ3ZCAxCiAgICAgICAgICAgICAgICBqbnoKICAgICAgICAgICAgICAgIHJ3ZCAxCiAgICAgICAgICAgICAgICBzdWIgMQogICAgICAgICAgICBqbnoKICAgICAgICAgICAgZndkIDIKICAgICAgICAgICAgam1wCiAgICAgICAgICAgICAgICBzdWIgMQogICAgICAgICAgICAgICAgcndkIDEKICAgICAgICAgICAgICAgIGFkZCAxCiAgICAgICAgICAgICAgICByd2QgMQogICAgICAgICAgICAgICAgYWRkIDEKICAgICAgICAgICAgICAgIGZ3ZCAyCiAgICAgICAgICAgIGpuegogICAgICAgICAgICBmd2QgMQogICAgICAgICAgICBqbXAKICAgICAgICAgICAgICAgIHJ3ZCAyCiAgICAgICAgICAgICAgICBqbXAKICAgICAgICAgICAgICAgICAgICBzdWIgMQogICAgICAgICAgICAgICAgICAgIGZ3ZCAxCiAgICAgICAgICAgICAgICAgICAgYWRkIDEKICAgICAgICAgICAgICAgICAgICByd2QgMQogICAgICAgICAgICAgICAgam56CiAgICAgICAgICAgICAgICBmd2QgMgogICAgICAgICAgICAgICAgam1wCiAgICAgICAgICAgICAgICAgICAgc3ViIDEKICAgICAgICAgICAgICAgICAgICByd2QgMgogICAgICAgICAgICAgICAgICAgIGFkZCAxCiAgICAgICAgICAgICAgICAgICAgZndkIDIKICAgICAgICAgICAgICAgIGpuegogICAgICAgICAgICAgICAgZndkIDEKICAgICAgICAgICAgam56CiAgICAgICAgICAgIGZ3ZCAzCiAgICAgICAgICAgIHN1YiAxCiAgICAgICAgam56CiAgICAgICAgcndkIDIKICAgICAgICBqbXAKICAgICAgICAgICAgc3ViIDEKICAgICAgICAgICAgcndkIDMKICAgICAgICAgICAgYWRkIDEKICAgICAgICAgICAgZndkIDMKICAgICAgICBqbnoKICAgICAgICBmd2QgMQogICAgICAgIHN1YiAxCiAgICBqbnoKICAgIGZ3ZCAyCmpuegpyd2QgNwpwdXQ&input=MjA&debug=on)
### Disassembled
```
set numin
set numout
add 1
fwd 1
add 1
fwd 6
get
sub 1
jmp
    jmp
        sub 1
        fwd 1
        add 1
        rwd 1
    jnz
    fwd 1
    sub 1
    rwd 2
    add 2
    jmp
        rwd 4
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        jmp
            sub 1
            rwd 3
            add 1
            rwd 1
            add 1
            fwd 4
        jnz
        rwd 3
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        add 2
        jmp
            rwd 5
            jmp
                rwd 1
                jmp
                    sub 1
                    fwd 2
                    add 1
                    rwd 2
                jnz
                fwd 1
                jmp
                    sub 1
                    rwd 1
                    add 1
                    fwd 1
                jnz
                rwd 1
                sub 1
            jnz
            fwd 2
            jmp
                sub 1
                rwd 1
                add 1
                rwd 1
                add 1
                fwd 2
            jnz
            fwd 1
            jmp
                rwd 2
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                fwd 2
                jmp
                    sub 1
                    rwd 2
                    add 1
                    fwd 2
                jnz
                fwd 1
            jnz
            fwd 3
            sub 1
        jnz
        rwd 2
        jmp
            sub 1
            rwd 3
            add 1
            fwd 3
        jnz
        fwd 1
        sub 1
    jnz
    fwd 2
jnz
rwd 7
put
```
Or in Brainfuck notation:
```
+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.
```
[Answer]
# C, ~~43~~ 42 bytes
*Saved 1 byte thanks to @Dennis*
Every answer is the same, I must do something different!
[Try it online!](https://ideone.com/yuS2JB)
```
a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}
```
Explanation: it's basically `a(n-a(n-2))+a(n-a(n-1))` but with swaggyundefinedbehavior (works on my phone (gcc) and ideone).
[Answer]
## Mathematica, 36 bytes
Byte count assumes ISO 8859-1 encoding and Mathematica's `$CharacterEncoding` set to `WindowsANSI` (the default on Windows; other settings might work as well, but some like `UTF-8` definitely don't).
```
±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))
```
Defines `±` as a unary operator.
I tried getting rid of the duplication, but ended up with the same byte count:
```
±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~15~~ 14 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
2Rạ⁸ß€$⁺Sµ1>?2
```
[Try it online!](http://jelly.tryitonline.net/#code=MlLhuqHigbjDn-KCrCTigbpTwrUxPj8y&input=&args=MTA) or [verify all test cases](http://jelly.tryitonline.net/#code=MlLhuqHigbjDn-KCrCTigbpTwrUxPj8yCjIwUsK1xbzDh-KCrEc&input=) (takes a few seconds).
### How it works
```
2Rạ⁸ß€$⁺Sµ1>?2  Main link. Argument: n (integer)
2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ß€              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.
```
[Answer]
## JavaScript (ES6), ~~45 Bytes~~ 34 Bytes
A recursive solution in ES6. Any golfing tips much appreciated.
```
a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1
```
Thank you to [/u/ismillo](http://reddit.com/u/ismillo) for shortening even further.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~14~~ ~~12~~ 11 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ịḣ2S;
1Ç⁸¡2ị
```
This is an iterative approach.
[Try it online!](https://tio.run/nexus/jelly#@/9wd/fDHYuNgq25DA@3H1poBOT////fyAAA) or [verify all test cases](https://tio.run/nexus/jelly#@/9wd/fDHYuNgq25DA@3P2rccWihEVDov5FB0KGtR/cAhZrWuP8HAA).
### How it works
```
1Ç¡2ị   Main link. Argument: n
1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.
ịḣ2S;   Helper link. Argument: A (array)
ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.
```
[Answer]
# Python, ~~45~~ 40 bytes
```
a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))
```
Simple naïve interpretation of the challenge.
*Saved 5 bytes thanks to @LeakyNun!*
[Answer]
# Haskell, ~~39~~ 37 Bytes
```
h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))
```
exactly like described in the challenge, using guards
[Answer]
# R, 50 bytes
```
a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))
```
Usage:
```
> a(1)
  1
> a(20)
  12
```
[Answer]
## CJam, ~~19~~ 18 bytes
```
XXri{_($2$$+}*]-3=
```
[Try it online!](http://cjam.aditsu.net/#code=XXri%7B_(%242%24%24%2B%7D*%5D-3%3D&input=20)
Uses the iterative approach.
[Answer]
## C#, 51 44 bytes
```
int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));
```
i wonder if this can be shortened by making it anonymous
thanks pinkfloydx33!
[Answer]
# Golfscript, 29 bytes
```
~[1 1]{..0=(=\..1=(=@+\+}@*2=
```
[Try it online!](http://golfscript.tryitonline.net/#code=flsxIDFdey4uMD0oPVwuLjE9KD1AK1wrfUAqMj0&input=MjA)
[Answer]
## 05AB1E, 29 bytes
An iterative solution.
```
XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è
```
[Try it online](http://05ab1e.tryitonline.net/#code=WMuGWMuGw41MPnbCr8KkeXMtw6jCr3nCr3nDjcOoLcOoK8uGfcKvwrk8w6g&input=MTY)
[Answer]
# APL, 20 bytes
```
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
```
Explanation:
```
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument     
         ∇¨          Recursive call on both again
       +/            Sum          
```
[Answer]
# VBA Excel 87 bytes
Non-recursive, since I want this to work for n=100000, say:
```
Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1
```
... and press `return` (byte #87) at the end of the line to get the `End Function` statement for "free". Note that B values are offset by -1 to avoid initializing for n=1 and 2.
Invoke in spreadsheet as normal, eg `=A(100000)` to get `48157`
The recursive version, **61 bytes**,
```
Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))
```
starts to get unreasonably slow for n>30, and couldn't be said to work at all for n>40.
[Answer]
# Ruby, 36 bytes
A direct implementation. Any golfing suggestions are welcome.
```
a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}
```
[Answer]
## Java 7, ~~68~~ ~~61~~ 51 bytes
17 saved thanks to Leaky Nun.
```
int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}
```
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), ~~9~~ ~~7~~ 5 bytes
~~**Non-competing**, since the language postdates the challenge.~~ Thanks to **Kenny Lau** for saving 4 bytes. Code:
```
ece+V
```
Expanded form (`V` is short for `11`):
```
a(n) = ece+
a(0) = 1
a(1) = 1
```
Code:
```
e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up
```
[Try it online!](http://oasis.tryitonline.net/#code=ZWNlK1Y&input=&args=MTAwMA). Calculates n = 1000 in 0.1 seconds.
[Answer]
## PowerShell v2+, ~~85~~ ~~79~~ 69 bytes
```
param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]
```
Takes input `$n`, sets `$b` to be an array of `@(1, 1)`, then enters a loop from `2 .. $n`. Each iteration we tack onto `$b` the latest calculation in the sequence with a simple `+=` and the definition of the sequence. We then output the appropriate number from `$b` (with a `-1` because arrays in PowerShell are zero-indexed). This works if `$n` is `1` or `2` because both of those values are pre-populated into the lower indices of `$b` from the start, so even if the loop tacks on junk, it's ignored anyway.
---
### Recursive solution ~~78~~ 76 bytes
```
$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}
```
First time I've used the equivalent of a lambda as the answer, as usually an iterative solution is shorter (as you can see from all the nested parens). ~~But, in this case, the nested parens are almost duplicated in the iterative solution with the nested array calls, so the recursive solution is shorter.~~ Nope, the iterative solution is indeed shorter (see above).
Call it via the execution-operator, like `&$a 20`. Just a straight-up recursive call.
[Answer]
## JavaScript (ES6), 66 bytes
```
n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])
```
Non-recursive version for speed; recursive version is probably shorter but I'll leave it for someone else to write. I always like it when I get to use `reduce`. Note: 1 byte saved by returning `true` (which casts to `1` when used in an integer context) for of `a(1)` and `a(2)`.
[Answer]
# Pyth, 16 bytes
```
L|<b3smy-bytdtBb
L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum
```
Defines a function `y`.
[Try it online](https://pyth.herokuapp.com/?code=L%7C%3Cb3smy-bytdtBbyMS20)
(added `yMS20` to print the first 20 values)
[Answer]
# Forth, 76 bytes
I finally got it working!
```
: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;
```
[**Try it online**](http://ideone.com/b8uJSr)
**Explanation:**
```
: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;
```
[**Try it online**](http://ideone.com/PmnJRO) (slightly un-golfed from above)
Unfortunately, [mutual recursion](https://en.wikipedia.org/wiki/Mutual_recursion) is a bit [too wordy](https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Calls-and-returns.html) to use for golfing.
[Answer]
## Lua, 59 bytes
```
function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end
```
[Answer]
# Maple, ~~43~~ 41 bytes
```
a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)
```
Usage:
```
> a(1);
  1
> a(20);
  12
```
This problem is certainly a good candidate for memoization. Using [option cache](https://www.maplesoft.com/support/help/maple/view.aspx?path=CacheOption), the run times are cut down significantly:
```
aC := proc(n) 
      option cache; 
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 ); 
end proc:
```
This can be seen using:
```
CodeTools:-Usage( aC(50) );
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 17 bytes
```
!¡λṁ!¹m≠→L¹↑_2)ḋ3
```
[Try it online!](https://tio.run/##ASoA1f9odXNr//8hwqHOu@G5gSHCuW3iiaDihpJMwrnihpFfMinhuIsz////MTU "Husk – Try It Online")
Feels too long. I'll post something with `fix` soon.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 20 bytes
No big shenanigans, just recursively calculates the result.
```
§2?1:ßU-ßUÉ)+ßU-ßU-2 
§2                   // If the input is less than or equal to 2
  ?1                 // return 1,
    :                // otherwise
     ß               // recursively recall with
      U-ßUÉ          // input minus recursive recall input minus one
           )+        // plus
             ßU-ßU-2 // same with input minus two.
```
[Try it here.](https://ethproductions.github.io/japt/?v=1.4.6&code=pzI/MTrfVS3fVckpK99VLd9VLTI=&input=MTU=)
[Answer]
# J, ~~29~~ 28 bytes
```
1:`(+&$:/@:-$:@-&1 2)@.(2&<)
```
Uses the recursive definition.
### Usage
Extra commands are used for formatting multiple input/output.
```
   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12
```
### Explanation
```
1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result
```
]