Recursive functions — the definitional route to "computable"

Parent: logic

The (partial) recursive functions

The smallest class of partial functions ℕᵏ → ℕ (over all k) that contains the basic functions

zero Z(x) = 0, successor S(x) = x+1, projections Pᵢ(x₁,…,xₖ) = xᵢ,

and is closed under three schemes:

Composition — from g of arity m and h₁,…,hₘ of arity k, form f(x₁,…,xₖ) = g(h₁(x₁,…,xₖ),…,hₘ(x₁,…,xₖ)).

Primitive recursion — from g of arity k and h of arity k+2, form f of arity k+1 by f(0, x) = g(x) and f(n+1, x) = h(n, f(n, x), x).

Minimization μ — from g of arity k+1, form f(x) = μn.[ g(n, x) = 0 ] = the least n with g(n,x)=0 (and g(i,x) defined and nonzero for i<n); undefined if no such n.

Three named subclasses fall out by which schemes you keep:

basics + composition + primitive recursion only → primitive recursive — all total (always halt);
add μ → general / μ-recursive = the partial recursive functions;
the total members of that class → total recursive.

Why "total recursive" is subtle

The total recursive functions = the computable functions that are total (halt on every input). Two non-obvious facts: (1) you cannot effectively list them — no algorithm enumerates exactly the total ones (diagonalize: build a total computable function outside any proposed list); (2) "is this program total?" is undecidable — in fact Π₂, harder than halting. So total recursive is a clean mathematical class with no algorithmic handle on membership — unlike the r.e. partial recursive functions, which you can enumerate.

What the ladder means

primitive recursive ⊊ total recursive ⊊ partial recursive. The first strict step has an explicit witness: Ackermann is total and computable but not primitive recursive (for-loops are too weak).
The top rung equals Turing machines and the λ-calculus — the Church–Turing thesis.
The jump is exactly bounded → unbounded recursion: primitive recursion = for-loops (total); adding μ = while-loops (Turing-complete, may not halt). That's the phase transition where undecidability appears.

(Illustration, now that the definition is fixed: factorial(0)=1, factorial(n+1)=(n+1)·factorial(n) is primitive recursion with g=1, h(n,y,·)=(n+1)·y.)