principleMinor
Inductive vs. recursive definition
Viewed 0 times
definitioninductiverecursive
Problem
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?
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?
Solution
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
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)$.
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)$.
Context
StackExchange Computer Science Q#13225, answer score: 3
Revisions (0)
No revisions yet.