Paired Tally Sequences

Two clerks keep intertwined tallies. Clerk F and clerk M each produce a sequence of non-negative integers defined by:

• F(0) = 1, M(0) = 0
• F(n) = n - M(F(n - 1)) for n > 0
• M(n) = n - F(M(n - 1)) for n > 0

Write tallies(n) returning the tuple (F(n), M(n)).

Examples

Input:  n = 5
Output: (3, 3)
Explanation: F = 1, 1, 2, 2, 3, 3 and M = 0, 0, 1, 2, 2, 3 for n = 0..5.

Input:  n = 0
Output: (1, 0)

Input:  n = 7
Output: (5, 4)

Constraints

• 0 <= n <= 1500
• With memoisation the recursion depth is about n + 1, under the ~3000 limit.

Goals

• Implement two functions that call each other
• Memoise both functions so the mutual recursion stays linear
• Reason about recursion depth when calls are nested inside arguments