Untuk fungsi \(f:\N \to \N\text{,}\) suatu definisi rekursif terdiri atas syarat awal beserta relasi rekurensi. Syarat awal adalah nilai \(f(0)\) yang diberikan secara eksplisit. Relasi rekurensi adalah rumus untuk \(f(n+1)\) dalam hal \(f(n)\) (dan mungkin juga \(n\) itu sendiri).