Is there any procedure saying "this function is not obtainable without using recursion at least n times"?

Question

It is known that $sum(x,y)=x+y$ is not obtainable from any compositions of basic functions $z,s,id^n_i$(zero, successor, projections) without using at least one recursion. also, $\times(x,y)=x\cdot y$ is not, without at least recursion twice.

I wonder if this can be extended to for any "at least $n$" cases. i.e., given any fucntion $f$, Is there a way testing this $f$ is not obtainable without using recursion at least $n$ times?

Answer 1

No, there is no way. Because you can build a recursive primitive function such that for some Turing Machine $M$

• $f(x,y)=0$ if $M$ does not halt in $x$ steps or less
• $f(x,y)=x+y$ if $M$ does halt in $x$ steps or less

Hence $f$ could use recursion at most $0$ times if $M$ does not halt or $2$ times if $M$ halts. But deciding if $M$ halts is not possible, so deciding how much recursions you need to compute $f$ is not decidable.