int highest(long long n) {
    int r = 0;
    while(n) {
        r++;
        n >>= 1;
    }
    return r-1;
}

int dfs(long long n) {
    if(n == 0) return 0;
    int h = highest(n);
    long long n1 = n-(1LL<<h);
    long long n2 = (1LL<<(h+1))-n;
    int res = 1+dfs(n1);
    if(n2 < n) res = min(res, 1+dfs(n2));
    return res;
}

What is complexity of dfs(n) and why?