6
$\begingroup$

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?

$\endgroup$
  • 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 '13 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 '13 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$ – AProgrammer Jul 13 '13 at 7:00
2
$\begingroup$

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

$\endgroup$
  • $\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$ – jmite Jul 17 '13 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 '13 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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