Find what level of the Calkin–Wilf tree a number is on The Calkin–Wilf tree is a tree of fractions where to get the two child nodes, the first child is (the parent's numerator / x) and the second child is (x / the parent's denominator), where x is the sum of the parent's numerator and denominator. (This part was added later so this question is more search-able)
It looks like this when the fractions are expressed as coordinates:
$$
\newcommand{\r}{→}
\newcommand{\s}{\quad}
\begin{align}
&(1, 1) \r \\
&\s(1, 2) \r \\
&\s\s(1, 3) \r \\
&\s\s\s(1, 4) \r\ \dots \\
&\s\s\s(4, 3) \r\ \dots \\
&\s\s(3, 2) \r \\
&\s\s\s(3, 5) \r\ \dots \\
&\s\s\s(5, 2) \r\ \dots \\
&\s(2, 1) \r \\
&\s\s(2, 3) \r \\
&\s\s\s(2, 5) \r\ \dots \\
&\s\s\s(5, 3) \r\ \dots \\
&\s\s(3, 1) \r \\
&\s\s\s(3, 4) \r\ \dots \\
&\s\s\s(4, 1) \r\ \dots
\end{align}
$$
So, I would like to find out if there is an algorithm to find the minimum number of times the rule has to be applied to get to a certain number.
Here are some patterns I have noticed (Where you are trying to get to $(a, b)$, and the function that returns the minimum times is $f(a, b)$, which is $-1$ where it is impossible)
f(a, b) = f(b, a)
f(1, b) = b - 1
f(a, a) = -1 (except when a = 1, as f(1, 1) = 0)
f(2, b) = -1 if b is even, else ceil(b / 2)
f(<prime number>, b) = -1 iff b is a multiple of a
f(3, b) = (-1 iff (b is a multiple of 3)), else (floor(n / 3) + 2)

If you arrange them in a table (Download here)
Rows are the same columns, as a and b can be reversed.
The diagonals from the top-left to the bottom-right are the same as a row / column.

I can make some brute-force code (In Python)
def minimise(a, b):
    if a < 1 > b:
        return -1
    possible = {(1, 1)}
    target = (a, b)
    i = 0
    get_nexts = next_getter_factory(target)

    while possible and target not in possible:
        possible = {next_pos for pos in possible for next_pos in get_nexts(*pos)}
        i += 1

    if not possible:
        return -1

    return i

def next_getter_factory(target):
    A, B = target
    def get_nexts(a, b):
        if a + b <= B:
            yield (a + b, b)
        if a + b <= A:
            yield (a, a + b)
    return get_nexts

This has the one optimization that it won't check a possibily if one of it's values is already above the target value, but there is probably some math that can make this happen in a reasonable amount of time with large input (I am expecting values up to $2^{128}$ as input).

Let $h(x,y)$ be the number of steps required to get to the pair $(x,y)$, assuming this is possible, or $h(x,y) = -1$ if $(x,y)$ is not reachable.
Clearly $h(x,y) = h(y,x)$, since you can always add in either direction, so we may as well assume $x \leq y$ when evaluating this function.
Also, if either $x$ or $y$ is less than $1$, then $h(x,y) = -1$.  And of course we also know $h(1,1) = 0$.
In fact, I guess we know that $h(1, x) = x-1$ for all positive integers $x$ (as you yourself pointed out!) since the only way to get to $(1,x)$ is by repeatedly adding $1$ to the second value in your pair.
OK. Assuming $a \leq b$, how could you possibly get to $(a,b)$?  Well, your last step would have to be $(a, b-a) \to (a,b)$, because going $(a-b, b) \to (a,b)$ wouldn't be possible (since $a-b \leq 0$).
So now consider the following Python code (Python 2):
def h(a, b):
    if a > b:
        return h(b, a) #can assume a <= b
    if a < 1:
        return -1 #can assume 1 <= a <= b
    if a == 1:
        return b - 1
    k = h(a, b - a)
    if k == -1:
        return -1
    return 1 + k

Basically, the number of steps to reach $(a,b)$, is however many steps it takes to reach $(a, b-a)$, plus $1$.  (Unless $(a, b-a)$ is impossible, in which case $(a,b)$ is, too.)
But if you look at this code for a little while, you'll realize that it's a little inefficient: if $b-a$ is still at least as big as $a$, then we'll just subtract $a$ again.  In fact we'll keep subtracting $a$ until we get to something less than $a$.  That result (the number that's less than $a$) is called the REMAINDER when we divide $b$ by $a$, and the number of times we subtract $a$ is called the QUOTIENT.
So we could improve the code somewhat:
def h(a, b):
    if a > b:
        return h(b, a) #can assume a <= b
    if a < 1:
        return -1 #can assume 1 <= a <= b
    if a == 1:
        return b - 1
    q, r = divmod(b, a)
    k = h(r, a) #now r < a
    if k == -1:
        return -1
    return q + k

At this point, hopefully you'll be able to see how Catalin Zara's response works.
