It means to define a function on the natural numbers by (a) defining it on zero outright, and (b) defining it on n+1 in terms of its definition on n. This suffices to define it on every natural number, a fact that can be proved by mathematical induction.

It is important because it connects induction with recursion in the most elemental way, and because it generalizes readily to other "data-driven" forms of reasoning/programming.

I don't know the origin of the term, but I suppose that recursion on the natural numbers is arguably the most primitive form of recursion.

Answer by Robert Harper:

It means to define a function on the natural numbers by (a) defining it on zero outright, and (b) defining it on n+1 in terms of its definition on n. This suffices to define it on every natural number, a fact that can be proved by mathematical induction.

It is important because it connects induction with recursion in the most elemental way, and because it generalizes readily to other "data-driven" forms of reasoning/programming.

I don't know the origin of the term, but I suppose that recursion on the natural numbers is arguably the most primitive form of recursion.

What is primitive recursion?

### Like this:

Like Loading...

*Related*