Computer solutions welcome,
though a proof would be better!

... once to get the first few values of f(n); then to use the Sloane encyclopedia; then to evaluate f(1,000,000,000,000).

The program below includes different subroutines to evaluate this function.  The first, function f(n) is defined recursively, just as presented in the puzzle, and was the first implemented, through n of about 50, when it began to slow down.

The first several (starting with f(0) are 0  1  1  2  3  3  4  4  5  6  6  7  8  8  9  9  10  11  11  12  12  13  14  14.

The Online Encyclopedia of Integer Sequences identified this as the Hofstadter G-sequence: a(n)=n-a(a(n-1)). It also gives some formulas for evaluating it without recursion or with minimal recursion or iteration.  The simplest is a(n)=floor(sigma*(n+1)) where sigma=(sqrt(5)-1)/2. That is implemented in the below program as function g(n).

Another method is given as

"Rule of construction for the sequence: a(n) = An, where An denotes the Fibonacci antecessor to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58)= 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002"

That rule is implemented in function h(x) below, for the curiosity of it. That will help explain it better.

The program, after adding the faster methods, first produces a comparison for the first 58 values of n:

 n  f(n)  g(n) h(n)
 1    1    1    1
 2    1    1    1
 3    2    2    2
 4    3    3    3
 5    3    3    3
 6    4    4    4
 7    4    4    4
 8    5    5    5
 9    6    6    6
10    6    6    6
11    7    7    7
12    8    8    8
13    8    8    8
14    9    9    9
15    9    9    9
16   10   10   10
17   11   11   11
18   11   11   11
19   12   12   12
20   12   12   12
21   13   13   13
22   14   14   14
23   14   14   14
24   15   15   15
25   16   16   16
26   16   16   16
27   17   17   17
28   17   17   17
29   18   18   18
30   19   19   19
31   19   19   19
32   20   20   20
33   21   21   21
34   21   21   21
35   22   22   22
36   22   22   22
37   23   23   23
38   24   24   24
39   24   24   24
40   25   25   25
41   25   25   25
42   26   26   26
43   27   27   27
44   27   27   27
45   28   28   28
46   29   29   29
47   29   29   29
48   30   30   30
49   30   30   30
50   31   31   31
51   32   32   32
52   32   32   32
53   33   33   33
54   33   33   33
55   34   34   34
56   35   35   35
57   35   35   35
58   36   36   36

showing that the given non-recursive and less-recursive methods match the recursively defined function.

Then it uses the evaluation a(n)=floor(sigma*(n+1)) where sigma=(sqrt(5)-1)/2, which finds f(1,000,000,000,000) = 618,033,988,750, which is the answer to this puzzle.

Then it evaluates using the "Fibonacci antecessor" method.  That "Zeckendorf expansion" merely means expressing n as a sum of Fibonacci numbers, always using the largest Fib. number that will fit.  The value of f(n) is then the sum of all the Fibonacci numbers that are the next lower than the ones used to sum to n. For 1,000,000,000,000 and f(1,000,000,000,000) these are:

956722026041  591286729879
 32951280099   20365011074
  7778742049    4807526976
  1836311903    1134903170
   701408733     433494437
     9227465       5702887
      832040        514229
      121393         75025
       46368         28657
        2584          1597
         987           610
         233           144
          89            55
          13             8
           3             2
           

The left column sums to 1,000,000,000,000, starting with the largest Fib. number under (or equal) that value, then the largest that is under or equal what is left, etc. until a Fib. number (3 in this case) is left.  The right column consists of the Fib. numbers that are just below the corresponding one on the left (for example, 610 is the Fib. number just prior to 987). They indeed add to 618,033,988,750, confirming the answer to this puzzle.

DECLARE FUNCTION f# (n#)
DECLARE FUNCTION g# (n#)
DECLARE FUNCTION fib# (x#)
DECLARE FUNCTION h# (x#)
DEFDBL A-Z
CLEAR , , 25000

DIM SHARED fi(75)
FOR i = 0 TO 75 ' fib(0) = fib(1) = 1
 fi(i) = fib(i)
NEXT

FOR x = 1 TO 58
 PRINT x; f(x); g(x); h(x)
 ' IF x MOD 40 = 0 THEN DO: LOOP UNTIL INKEY$ > ""
NEXT

PRINT g(1000000000000#)
PRINT h(1000000000000#)

FUNCTION f (n)
 IF n = 0 THEN
  f1 = 0
 ELSE
  f1 = n - f(f(n - 1))
 END IF
 f = f1
END FUNCTION

FUNCTION fib (x)
 pf = 0: cf = 1
 FOR i = 1 TO x
   nf = pf + cf
   pf = cf: cf = nf
 NEXT
 fib = cf
END FUNCTION

FUNCTION g (n)
 g = INT((n + 1) * (SQR(5) - 1) / 2)
END FUNCTION

FUNCTION h (x)
 tot = x: tot2 = 0
 DO
   i = 1
   DO
    IF fi(i) > tot THEN EXIT DO
    i = i + 1
   LOOP
   tot2 = tot2 + fi(i - 2)
   tot = tot - fi(i - 1)
   IF x > 1000 THEN PRINT USING "##############"; fi(i - 1); fi(i - 2)
 LOOP UNTIL tot = 0
 h = tot2
END FUNCTION