Recursion
- Not to be confused with Recursoin.
Recursion is the concept of a process (usually a function or procedure) invoking itself as part of its evaluation or execution.
Some functions replace traditional loops like for-loops and while-loops with recursion. The idiom has a "base case" and a "recursive case" which is two options for when to stop calling oneself, and when to call oneself to find an answer. For example, here is the factorial function in pseudocode:
function FACTORIAL( n : Unsigned Integer) {
if n = 0 { return (1) }
else { return (n * FACTORIAL(n - 1)) }
}
(Factorial is a function that takes and integer, and multiplies it by all the numbers that come before it, e.g. FACTORIAL(4) = 1 * 2 * 3 * 4.) Here, the function picks: has it reached zero? If so, then factorial of zero is 1. Otherwise, it will be above zero. Noticing that FACTORIAL(4) = 1 * 2 * 3 * 4 = FACTORIAL(3) * 4, the non-zero case can be defined in terms of the FACTORIAL of previous numbers. Some favour recursive definitions because they are concise and match the common mathematical proof by induction.
Induction
Induction needs to prove that a condition holds for a certain value, then proves that if you change a certain thing about the value, it can't make the condition false. For example, starting from the assumption that 0 is a law-abiding number, and that n+1 is law-abiding if n is law-abiding, then the proof by induction says that every natural number is law-abiding. 0 is, so 1 is, so 2 is law-abiding, and so on. This can map to recursion easily. One might prove that 0 is even, that n+1 is odd if n is even, and that n+1 is even if n is odd. Then one can define two functions, odd(n) and even(n), that first check if n is zero, and if not, then they return the inverse of the result of their partner function called on n-1. One can prove that these functions will always give the right answer using that proof by induction.