# Inductive vs. recursive definition

When should I call a definition recursive and when should I call it inductive?

I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like natural numbers, lists, trees, etc. as inductive whereas we refer to definitions of operations over objects like $+$ or $head$ or $leftchild$ as recursive.

Is this the correct way to distinguish these in programming languages theory?

Are there examples where using either would make sense?

• Inductive definitions specify sets by means of fixpoints. Recursive definitions specify individual objects (i.e. their "construction") and don't use fixpoints. Jul 11, 2013 at 14:33
• ezyang discusses the difference here: blog.ezyang.com/2013/04/… I don't get it, but perhaps someone will find it useful. Jul 11, 2013 at 19:54
• I tend to think as recursion as starting from the unknown and going to the known while induction starts from the known and builds the unknown. Jul 13, 2013 at 7:00

An inductive definition takes some elementary objects of the structure to be defined and combines those to obtain new elements of said structure.

Example: Definition of the syntax of many logics.

On the contrary, a recursive definition is a rule how to obtain a specific object based on somehow "smaller" objects of the same structure.

To see the difference more clearly, consider the following: To define the valid arithmetical expressions, you would state something like

• Any real number is a valid arithmetical expression
• When $\varphi$ and $\psi$ are valid arithmetical expressions, so are $(\varphi + \psi)$, $(\varphi - \psi)$, etc.

This is an inductive definition of arithmetic expressions, as you build up the class of valid expressions from the bottom (base cases) upwards. Recursion, on the other hand, works from the top to the bottom. In this case, you would recursively check whether an arbitrary string is a valid expression or not.

When you define an object recursively, the object is determined by easier to compose objects of the same structure, like the Fibonacci numbers. You can only get the value of $\text{Fib}(n)$ by knowing $\text{Fib}(n-1)$ and $\text{Fib}(n-2)$.

• So if I'm understanding right, Induction is a form of composition, forming larger objects from smaller ones, while recursion is a form of decomposition, breaking a larger object into smaller parts? Jul 17, 2013 at 15:44
• Yeah, you could say that induction and recursion are different perspectives on the same method. Induction works bottom-up, and recursion works top-down.
– Rmn
Jul 18, 2013 at 8:51