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".

  • $\begingroup$ 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. $\endgroup$
    – Merbs
    Commented Oct 23, 2012 at 3:05
  • $\begingroup$ Inductively usually means recursively from $n$ to $n+1$, so recursively is the more general adverb. $\endgroup$ Commented Oct 23, 2012 at 3:34
  • $\begingroup$ What kind of recursively is not inductively, @YuvalFilmus? $\endgroup$
    – Tim
    Commented Oct 23, 2012 at 3:43
  • $\begingroup$ @YuvalFilmus: That's a very limited notion of inductive. $\endgroup$ Commented Oct 23, 2012 at 11:12
  • $\begingroup$ To me they mean the same thing out of context. In a specific context, they might mean different things. $\endgroup$ Commented Oct 23, 2012 at 21:38

3 Answers 3


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)
     return 1 + collatz(3 * n + 1)

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.


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

  • $\begingroup$ so "recursion = divide and conquer", which first top-down and then bottom-up? $\endgroup$
    – Tim
    Commented Oct 23, 2012 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.

  • $\begingroup$ Induction is not only about proofs. You also use it all the time to inductively define recursive structures (data structures, languages, etc) $\endgroup$
    – hugomg
    Commented Nov 15, 2012 at 12:09
  • $\begingroup$ @missingno Please provide a source for that definition. $\endgroup$
    – Tom
    Commented Nov 17, 2012 at 0:24
  • $\begingroup$ 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:" $\endgroup$
    – hugomg
    Commented Nov 17, 2012 at 17:42
  • $\begingroup$ @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' $\endgroup$
    – Tom
    Commented Nov 19, 2012 at 15:47
  • $\begingroup$ 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... $\endgroup$
    – hugomg
    Commented Nov 20, 2012 at 1:04

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.