# Recursion

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