Recursion: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 21:22, 3 January 2019

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.

@@ Line 1: / Line 1: @@
-{{trope}}
+{{Useful Notes}}
-Recursion means an item repeats in a self-similar way.
+[[Recursion]] means an item repeats in a self-similar way.
-A [[Useful Notes/Mathematics|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:
+A [[Mathematics|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.
@@ Line 11: / Line 11: @@
 Subtropes include [[Recursive Reality]]. Can induce a [[Mind Screw]].
-If you don't already understand this concept, see also [[Recursion]].
+If you don't already understand this concept, see also [[Recursion#top|Recursion]].
 {{reflist}}
-[[Category:Self Demonstrating Article]]
 [[Category:Recursion]]
-[[Category:Trope]]
+[[Category:Self-Demonstrating Article]]
+[[Category:Mathematics]]