Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Do "inductively" and "recursively" mean very similar?

For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having been determined, and is initialized with the first component, would you call it works recursively or inductively? I have been using "recursively", but today someone said it "inductively".

share|improve this question
    
This article on Induction and Recursion summarizes it nicely, but the gist is that they're closely related; a mathematical induction proof can be written as a recursive algorithm. –  Merbs Oct 23 '12 at 3:05
    
Inductively usually means recursively from $n$ to $n+1$, so recursively is the more general adverb. –  Yuval Filmus Oct 23 '12 at 3:34
    
What kind of recursively is not inductively, @YuvalFilmus? –  Tim Oct 23 '12 at 3:43
    
@YuvalFilmus: That's a very limited notion of inductive. –  Dave Clarke Oct 23 '12 at 11:12
    
To me they mean the same thing out of context. In a specific context, they might mean different things. –  Gilles Oct 23 '12 at 21:38

3 Answers 3

up vote 5 down vote accepted

No, but not for the reasons other people have given. The difference between recursion and induction is not that recursion is "top-down" and induction is "bottom-up." Induction is isomorphic to something called "primitve recursion," but, in general, recursion is strictly more powerful than induction.

The distinction between top-down and bottom up is trivial -- any "top-down" primitive recursive program can be mechanically converted into something "bottom-up." In fact, any proof by induction can be turned into a recursive program. In the framework of the calculus of inductive constructions, if you want to prove that every natural number is froopulous, you'd write it as a function that constructs a proof that n is froopulous by making a recursive call to construct a proof that n-1 is froopulous.

The key factor of induction is that things are defined in terms of smaller things, and they "bottom out" after finitely many steps. Natural numbers are inductive because every natural is either 0, or the successor of a smaller natural. Lists are inductive because every list is either empty, or can be broken down ("unfolded") into an element and a smaller list.

Sometimes recursive programs aren't written in terms of smaller things though. For example, take this Collatz funtion:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

This function goes neither top-down nor bottom-up, and is thus not inductive over the natural numbers.

There might be an ordering to treat that inductively, but for most things there's simply no way. Functions over infinite streams are a great example. In fact, streams are the prototypical example of a "coinductive" type.

Bob Harper's "Practical Foundations for Programming Languages," available free online, has a nice introduction to inductive, coinductive, and recursive types.

share|improve this answer

To me it mostly is a question of viewpoint. If I define objects based on smaller one, I do it inductively, so that is bottom-up. If I solve a problem by breaking it down in smaller pieces that are solved in the same manner I call it recursion, that is top-down.

(edit) PS. See a similar question in our Mathematics sister department, Recursive vs. inductive definition. I quote from the answer of Carl Mummert:

My best description is that "inductive definition" is more common when we are defining a set of objects "out of nothing", while "recursive definition" is more common when we are defining a function on an already-existing collection of objects.

But more importantly:

it's not worth losing sleep over

share|improve this answer
    
so "recursion = divide and conquer", which first top-down and then bottom-up? –  Tim Oct 23 '12 at 15:53

No, they're not the same. And you're right (I'm assuming about the algorithm you're describing): it's recursive.

The reason is the definition of both words, which you can read in a dictionary or Wikipedia.

Induction (assuming 'mathematical induction') is specifically about proving that all cases of an argument are true.

Recursion is specifically about a process maybe being repeated in some way within the same process.

RE: other people's answers:

After seeing other people's answers, I can understand why there's confusion: when defining datastructures, functions, and languages some theorists seem to use 'inductive' and 'recursive' in a confusing way (see comments to this question). I don't think Koppel's answer (even with current highest votes) really reflects that confusion. Since we are talking about an algorithm, I wouldn't say there are 'inductive algorithms'; I think that's an unnecessary categorization.

share|improve this answer
    
Induction is not only about proofs. You also use it all the time to inductively define recursive structures (data structures, languages, etc) –  hugomg Nov 15 '12 at 12:09
    
@missingno Please provide a source for that definition. –  Tom Nov 17 '12 at 0:24
    
One example I could think of is here: " The language of \mathcal{L}, also known as its set of formulæ, well-formed formulas or wffs, is inductively defined by the following rules:" –  hugomg Nov 17 '12 at 17:42
    
@missingno which leads to this Wikipedia page where I think there's a redundant and confusing use of the word 'inductive', essentially being used as 'recursive' –  Tom Nov 19 '12 at 15:47
    
Please don't make me look for even more examples. Even though you might not agree with it, its definitely a very common idiom and you can find it in many books too if you look for it. And its not like someone edited the wikipedia article on purpose to prove my point... –  hugomg Nov 20 '12 at 1:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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