What is primitive recursion?

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?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s