Recursion

Recursion means an item repeats in a self-similar way.

A mathematical function made with recursion, also called induction, involves defining some values with one or more base cases and defining the rest in terms of other values of the same function. For example, the factorial function x! is defined with the following rules:

0! = 1
x! = x * (x - 1)!, that is, a number's factorial is the number times the previous number's factorial.

Thus, 1! = 1 * 0! = 1, 2! = 2 * 1! = 2, 3! = 3 * 2! = 6, 4! = 4 * 3! = 24, 5! = 5 * 4! = 120, etc.

Recursion in computer science involves a method, function, or subroutine calling itself. For example, a "flood fill" or "paint bucket" tool fills matching pixels to the left and to the right and then applies the tool to the pixels above and below the pixels that were changed. Programs written in languages descended from Lisp make heavy use of recursion.

Subtropes include Recursive Reality. Can induce a Mind Screw.

If you don't already understand this concept, see also Recursion.