What are the guidelines/tips for calculating the complexity of a chained-recursive function?

I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler.

In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we want to know precisely what the output of $f$ is. For example, we can prove by induction that f1 will always output 1.

Now, replace each inner recursive call to $f$ with the value it returns. In the f1 case, we replace f1(f1(n/2) + f1(n/3) - f1(n/5)) by f1(1+1-1) which is simplified to f1(1). This means that we did a total of 4 calls to $f$, and for each call to $f$ we know exactly what the input was. Here, in this example, the inputs are $n/2,n/3,n/5,1$.

Finally, we can start calculating the time complexity: since we know how many recursive calls happened and what input was there for each recursive call, we can build a recursive formula for the time complexity. In the case of f1, it will be: $T(n)=T(n/2)+T(n/3)+T(n/5)+T(1)+c$, since we add a recursive call with the input of f1 for each time f1 was invoked.

This can be solved using traditional techniques, such as the master theorem.

If k ≤ 1 then we are stuck; there will be infinite recursion unless the input is n = 0 for k = 0.

Otherwise: The result is 1 if $n < k \cdot 2^m$, for every m ≥ 0. Proof by induction: It is obviously true if m = 0. Assume it is true for all m' ≤ m: Let $n < k \cdot 2^{m+1}$. If $n < k \cdot 2^m$ then the result is 1 by induction. Otherwise we calculate f(n/2), f(n/3), f(n/5), each argument less than $k \cdot 2^m$, so the three results are 1, and the final result is 1.

With the result always being 1, we can try to find the complexity using the master theorem. It will be proportional to $n^{1/2 + 1/3 + 1/5}$ = $n \cdot n^{1/30}$

For your $f_1$, you need to solve the recurrence

$$T(n)=\begin{cases}n<k\to T(1)\\n\ge k\to T(f_1(\frac n2) + f_1(\frac n3) - f_1(\frac n5))+T(\frac n2)+T(\frac n3)+T(\frac n5).\end{cases}$$

This mandates the resolution of the recurrence on $f_1$ itself, probably not the easiest thing.

Your second example is contrived. "$\frac nc$ for some code" could just be written $g(n)$, and $$n\ge k\to T(n)=T(g(n))+U(n)+c$$ where $U$ is the "known complexity".

Update:

As shown by others, one can check that $f_1(n)=1$ for all $n$. So the recursion simplifies to

$$T(n)=\begin{cases}n<k\to T(1)\\n\ge k\to T(1)+T(\frac n2)+T(\frac n3)+T(\frac n5).\end{cases}$$