CJam, 14 bytes

CJam is much younger than this challenge, so this answer is not eligible for the green checkmark. However, it's quite rare that you get to use j this nicely, so I wanted to post it anyway.

l~2,{_(jj-j)}j

Test it here.

Explanation

j is basically the "memoised recursion operator". It takes an integer N, an array and a block F. The array is used to initialise the memoisation: the element at index i will be returned for F(i). j then computes F(N), either by looking it up, or by running the block (with n on the stack) if the value hasn't been memoised yet. The really nifty feature is that within the block, j only takes an integer i, and calls F(i) recursively. So here is the code:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";