# Do "inductively" and "recursively" have very similar meanings?

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

• 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. Oct 23 '12 at 3:05
• Inductively usually means recursively from $n$ to $n+1$, so recursively is the more general adverb. 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. 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. Oct 23 '12 at 21:38

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.

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

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