Very nice problem! Here is my solution that I found during the TST: Let's notice first that $\gcd(f(k),f(k+1))=1$ for all $k\in \Bbb{N^*}$. Indeed, if there was a pair $(a,b)=(f(s),f(s+1))$ with $\gcd(a,b)>1$, then we could choose the pair with $a+b$ minimal, but that pair should come from $(a,b-a)$ or $(a-b,b)$, which is a contradiction with the minimality of our choice. The crucial idea is to begin with the following induction hypothesis: (which is much stronger than what the conclusion suggest) For each pair $(m,n)$ of relatively prime numbers there is a unique $s\in \Bbb{N^*}$ such that $f(s)=m$ and $f(s+1)=n$. The proof is by induction on $m+n$. The base step is trivial, and for the induction step we distinguish two cases: $\bullet$ if $m>n$, then there is a $t\in \Bbb{N^*}$ such that $f(t)=m-n$ and $f(t+1)=n$, which implies $f(2t+1)=m$ and $f(2t+2)=n$; $\bullet$ if $m<n$, then there is a $t\in \Bbb{N^*}$ such that $f(t)=m$ and $f(t+1)=n-m$, which implies $f(2t)=m$ and $f(2t+1)=n$; In both situations the uniqueness of $s$ results (obviously) from $t$'s one. Now we just have to see that the number of pairs $(m,n)$ with $m+n=k$ and $\gcd(m,n)=1$ is exactly $\varphi(k)$ because $\gcd(x,k)=gcd(x,k-x)$ for all positive integers $x$.

As a continuation of the topic, I offer to solve the following problem. Let $g$ be another function of the set of positive integers into itself, defined by $g(1) = 1$, $g(2n) = g(n)$ and $g(2n + 1) = g(n) + g(n + 1)$ if $n+1$ is not an integer power of $2$ and $g(2n + 1) = 1$ if it is. Show that, for any odd positive integer $n$, the numbers $g(n)$ and $f(n)$ are coprime. Moreover, each pair $(p,q)$ of coprime integers, $0<p \le q$, occurs exactly one time among the pairs $(g(n),f(n))$ for odd $n$.

Straightforward but nice functional equation. Claim: For every $n \geq 1$, $\gcd(f(n), f(n+1)) = 1$. Proof: By strong induction. We can compute $f$ manually for $n \leq 3$. Now, \begin{align*} \gcd(f(2n), f(2n+1)) &= \gcd(f(n), f(n)+f(n+1)) = 1 \\ \gcd(f(2n+1), f(2n+2)) &= \gcd(f(n+1), f(n)+f(n+1)) = 1. \end{align*} Claim: There do not exist distinct positive integers $m, n$ such that $\{f(n), f(n+1)\} = \{f(m), f(m+1)\}$. Proof: Assume otherwise, and let $(m, n)$ be such a pair with $m+n$ minimal. We only check the case $(m, n) = (2m', 2n')$; the other parity cases follow similarly. In this case, $f(n) < f(n+1)$ and $f(m) < f(m+1)$, so it follows that \begin{align*} f(m') = f(m) = f(n) = f(n') \\ f(m'+1) = f(m+1)-f(m) = f(n+1) - f(n) = f(n'+1). \end{align*}So $(m', n')$ is another such pair with $m'+n' < m+n$, contradiction. $\blacksquare$ Fix $n$ now. For any positive integer $m$ with $f(2m+1) = n$, we must have $\{f(m), f(m+1)\} = \{n-k, k\}$ for some $\gcd(n, k) = 1$ by the first claim. There are at most $\phi(n)$ such pairs and thus $\phi(n)$ integers $m$ by the second claim, which gives the desired result.