MATL, 23 bytes

1Oiq:"@XJth"yy0)Q)_J+hw

Try it online!

Explanation

Each sequence is kept in an array. For each index n the new term of each sequence is computed and attached to the corresponding array. A for loop with N−1 terms is used, where N is the input number.

The update for sequence M needs to be done first. This is because F is always greater than or equal to M, so if we tried to update F first we would need a term of M not computed yet.

The code for the updating is reused by applying a for loop with two iterations and swapping the sequences in the stack.

1        % Push 1: seed for F sequence
O        % Push 0: seed for M sequence
iq:      % Input N. Generate range [1 2 ... N-1]
"        % For each (i.e. iterate N-1 times)
  @      %   Push current index, n (starting at 1 and ending at N-1)
  XJ     %   Copy to clipboard J
  th     %   Duplicate and concatenate. This generates a length-2 array
  "      %   For each (i.e. iterate twice)
    yy   %   Duplicate top two elements, i.e. F and M sequences
    0)   %     In the *first* iteration: get last entry of M, i.e M(n-1)
    Q)   %     Add 1 and index into F. This is F(M(n-1))
    _J+  %     Negate and add n. This is n-F(M(n-1)), that is, M(n)
    h    %     Concatenate to update M
    w    %     Swap top two elements, to bring F to top.
         %     In the *second* iteration the procedure is repeated to update F,
         %     and then the top two elements are swapped to bring M to top again,
         %     ready for the next iteration of the outer loop
         %   End for implicitly
         % End for implicitly
         % Display implicitly from bottom to top: first line is F, second is M

Python 2, 79 bytes

a=0,;i,=b=1,
exec"i+=1;a+=i/2-b[a[i/2-1]],;a,b=b,a;"*~-input()*2
print b,'\n',a

Iterative rather than recursive, because why not. The first line has a trailing space - if that's not okay it can be fixed for an extra byte.

Here are some combined lambdas which didn't really help:

f=lambda n,k:n and n-f(f(n-1,k),k^1)or k
f=lambda n,k:[k][n:]or f(n-1,k)+[n-f(f(n-1,k)[-1],k^1)[-1]]

Both take n and a parameter k either 0 or 1, specifying male/female. The first lambda returns the nth element, and the second lambda returns the first n elements (with exponential runtime).

Python 2, 107 bytes

F=lambda n:n and n-M(F(n-1))or 1
M=lambda n:n and n-F(M(n-1))
n=range(input())
print map(F,n),'\n',map(M,n)

Try it online

Larger input values cause a RuntimeError (too much recursion). If this is a problem, I can write a version where the error doesn't happen.

JavaScript (ES6), 75 bytes

g=n=>--n?([f,m]=g(n),m=[...m,n-f[m[n-1]]],[[...f,n-m[f[n-1]]],m]):[[1],[[0]]

I could save 2 bytes if I was allowed to return the Male sequence first:

g=n=>--n?([f,m]=g(n),[m=[...m,n-f[m[n-1]]],[...f,n-m[f[n-1]]]]):[[1],[[0]]

Perl 5.10, 85 bytes

Meh, dunno if I have more ideas to golf this down...

@a=1;@b=0;for(1..<>-1){push@a,($_-$b[$a[$_-1]]);push@b,($_-$a[$b[$_-1]]);}say"@a\n@b"

Try it online !

I had to add use 5.10.0 on Ideone in order for it to accept the say function, but it doesn't count towards the byte count.

It's a naive implementation of the algorithm, @a being the "female" list and @b the "male" list.

J, 47 bytes

f=:1:`(-m@f@<:)@.*
m=:0:`(-f@m@<:)@.*
(f,:m)@i.

Uses the recursive definition. The first two lines define the verbs f and m which represent the female and male functions, respectively. The last line is a verb that takes a single argument n and outputs the first n terms of the female and male sequences.

Usage

   (f,:m)@i. 5
1 1 2 2 3
0 0 1 2 2
   (f,:m)@i. 10
1 1 2 2 3 3 4 5 5 6
0 0 1 2 2 3 4 4 5 6

Haskell, 57 bytes

l#s=scanl(\a b->b-l!!a)s[1..]
v=w#1
w=v#0
(<$>[v,w]).take

Usage example: (<$>[v,w]).take $ 5 -> [[1,1,2,2,3],[0,0,1,2,2]]

The helper function # builds an infinite list with starting value s and a list l for looking up all further elements (at index of the previous value). v = w#1 is the female and w = v#0 the male sequence. In the main function we take the first n elements of both v and w.

Mathematica, 69 62 bytes

Thanks to Sp3000 for suggesting a functional form which saved 14 bytes.

k_~f~0=1-k
k_~f~n_:=n-f[1-k,f[k,n-1]]
Print/@Array[f,{2,#},0]&

This defines a named helper function f and then evaluates to an unnamed function which solves the actual task of printing both sequences.

Clojure, 132 131 bytes

(fn [n](loop[N 1 M[0]F[1]](if(< N n)(let[M(conj M(- N(F(peek M))))F(conj F(- N(M(peek F))))](recur(inc N)M F))(do(prn F)(prn M)))))

Simply builds the sequences iteratively up from zero to n.

Ungolfed version

(fn [n]
  (loop [N 1 M [0] F [1]]
    (if (< N n)
      (let [M (conj M (- N (F (peek M))))
            F (conj F (- N (M (peek F))))]
        (recur (inc N) M F))
      (do
        (prn F)
        (prn M)))))

Pyth, 24 bytes

It is probably impossible to use reduce to reduce the byte-count.

Straightforward implementation.

L&b-b'ytbL?b-by'tb1'MQyM

Try it online!

How it works

L&b-b'ytb  defines a function y, which is actually the male sequence.

L          def male(b):
 &b            if not b: return b
   -b          else: return b-
     'ytb            female(male(b-1))


L?b-by'tb1 defines a function ', which is actually the female sequence.

L          def female(b):
 ?b            if b:
   -by'tb          return b-male(female(b-1))
         1     else: return 1


'MQ        print(female(i) for i from 0 to input)
yMQ        print(male(i) for i from 0 to input)

Brachylog, 65 bytes

:{:1-:0re.}fL:2aw,@Nw,L:3aw
0,1.|:1-:2&:3&:?--.
0.|:1-:3&:2&:?--.

My attempt at combining both predicates for male and female into one actually made the code longer.

You could use the following one liner which has the same number of bytes:

:{:1-:0re.}fL:{0,1.|:1-:2&:3&:?--.}aw,@Nw,L:{0.|:1-:3&:2&:?--.}aw

Note: This works with the Prolog transpiler, not the old Java one.

Explanation

Main predicate:

:{:1-:0re.}fL                Build a list L of integers from 0 to Input - 1
             :2aw            Apply predicate 2 to each element of L, write the resulting list
                 ,@Nw        Write a line break
                     ,L:3aw  Apply predicate 3 to each element of L, write the resulting list

Predicate 2 (female):

0,1.                         If Input = 0, unify Output with 1
    |                        Else
     :1-                     Subtract 1 from Input
        :2&                  Call predicate 2 with Input - 1 as argument
           :3&               Call predicate 3 with the Output of the previous predicate 2
              :?-            Subtract Input from the Output of the previous predicate 3
                 -.          Unify the Output with the opposite of the subtraction

Predicate 3 (male):

0.                           If Input = 0, unify Output with 0
  |                          Else
   :1-                       Subtract 1 from Input
      :3&                    Call predicate 3 with Input - 1 as argument
         :2&                 Call predicate 2 with the Output of the previous predicate 3
            :?-              Subtract Input from the Output of the previous predicate 3
               -.            Unify the Output with the opposite of the subtraction

ES6, 89 85 83 bytes

2 bytes saved thanks to @Bálint

x=>{F=[n=1],M=[0];while(n<x){M.push(n-F[M[n-1]]);F.push(n-M[F[n++-1]])}return[F,M]}

Naïve implementation.

Explanation:

x => {
    F = [n = 1], //female and term number
    M = [0]; //male
    while (n < x) {
        M.push(n - F[M[n - 1]]); //naïve
        F.push(n - M[F[n++ - 1]]); //post-decrement means n++ acts as n in the calculation
    }
    return [F, M];
}

Ruby, 104 92 97 bytes

f=->n{n>0?n-m[f[n-1]]:1}
m=->n{n>0?n-f[m[n-1]]:0}
->n{a=(0...n);p(a.map{|i|f[i]},a.map{|i|m[i]})}

The third function prints first an array of the first n terms of f, followed by an array of the first n terms of m

These functions are called like this:

> f=->n{n>0?n-m[f[n-1]]:1}
> m=->n{n>0?n-f[m[n-1]]:0}
> s=->n{a=(0...n);p(a.map{|i|f[i]},a.map{|i|m[i]})}
> s[10]
[1, 1, 2, 2, 3, 3, 4, 5, 5, 6]
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6]

Java 169 Bytes total

int f(int n,int i){return n>0?n-f(f(n-1,i),-i):i>0?1:0;}void p(int n,int i){if(n>0)p(n-1,i);System.out.print(i==0?"\n":f(n,i)+" ");}void p(int n){p(n,1);p(0,0);p(n,-1);}

F(),M() 56 Bytes

int f(int n,int i){
    return n>0?n-f(f(n-1,i),-i):i>0?1:0;
}

recursive-for-loop and printing 77 Bytes

void p(int n,int i) {
    if(n>0) {
        p(n-1,i);
    }
    System.out.print(i==0?"\n":f(n,i)+" ");
}

outputting the lists in two different lines 37 Bytes

void p(int n) {
    p(n,1);
    p(0,0);
    p(n,-1);
}

input : p(10)
output :

1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9