The article is specifically talking about primitive-recursion versus non-primitive recursion. Primitive recursion is when we only recurse on a "smaller part" of

The article is specifically talking about primitive-recursion versus non-primitive recursion. Primitive recursion is when we only recurse on a "smaller part" of our argument; e.g. the tail of a list, or subtracting 1 from a natural number, or the children of a tree node, etc. We cannot, say, recurse on the next state of a Turing Machine; since that's not a "smaller part" of the previous state. Primitive recursion is equivalent to a 'for' loop with a pre-computed bound, e.g. 'for i in [0..X]: ...'. Recursion that's "non-primitive" would include general recursion, which places no restriction on how we recurse; e.g. we could recurse on the next state of a Turing Machine. General recursion is equivalent to a 'while' loop which re-computes its condition after each iteration. "Non-primitive" recursion can also include other restricted forms of recursion, which do not allow general computation, but cannot be represented by a primitive-recursive form; for example, the (usual definition of the) Ackermann function mentioned in the article takes two arguments, and its recursive calls can increase the second argument (so it's not primitive recursive). However, the pair of arguments always decrease according to (x, y) < (x, y+1) (if the first argument stays the same, the second argument must decrease) and (x, y) < (x+1, z) (if the first argument decreases, we can use anything for the second argument). The latter condition is so permissive that the Ackermann function is allowed to recurse with a second argument that is itself the result of another recursive call. This grows so fast that the number of loop iterations required to implement it cannot be computed by a primitive-recursive function (whatever function we try, there will eventually be an input that requires more iterations than that function returns).