2

What is the difference between recursion and induction? I have heard those terms used interchangeably, but I was wondering if there is a difference between them, and if so, what the difference is.

user107952
  • 20,508
  • To proceed recursively is essentially to work backwards, while proceeding inductively is to essentially work forwards, in some sense. At least, that's my understanding of it. – PrincessEev Aug 04 '20 at 00:04
  • Probably, main is which definitions and from where you take? https://en.wikipedia.org/wiki/Recursion and https://en.wikipedia.org/wiki/Induction maybe is not good source, but gives some impression. – zkutch Aug 04 '20 at 00:06

1 Answers1

9

In my experience:

  • "Recursion" is a way of defining some mathematical object (including a function or computation whose definition involves a recursive algorithm);
  • "Induction" is a way of proving some mathematical statement.

Extremely often, if a mathematical statement is made about a recursively-defined object, then the proof of that statement will involve induction.

For example, the definition of the Fibonacci numbers is a recursive definition. The proof of the assertion that the $n$th Fibonacci number is at most $2^n$ is an inductive proof.

Greg Martin
  • 78,820
  • I did searches on Math Overflow for “inductive definition” and “recursive definition”. There were 43 and 65 respectively. – MJD Aug 04 '20 at 01:06
  • 2
    That is my usage and what I would call careful usage, but the OP is not wrong in saying that the terms are often used interchangeably. When asked I certainly recommend that usage, but that ship has probably sailed. – Brian M. Scott Aug 04 '20 at 02:42