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?

  • 2
    $\begingroup$ Inductive definitions specify sets by means of fixpoints. Recursive definitions specify individual objects (i.e. their "construction") and don't use fixpoints. $\endgroup$
    – Raphael
    Jul 11, 2013 at 14:33
  • $\begingroup$ ezyang discusses the difference here: blog.ezyang.com/2013/04/… I don't get it, but perhaps someone will find it useful. $\endgroup$
    – Heatsink
    Jul 11, 2013 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 13, 2013 at 7:00

1 Answer 1


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)$.

  • $\begingroup$ 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? $\endgroup$ Jul 17, 2013 at 15:44
  • $\begingroup$ Yeah, you could say that induction and recursion are different perspectives on the same method. Induction works bottom-up, and recursion works top-down. $\endgroup$
    – Rmn
    Jul 18, 2013 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.