Recursion - Revision history

Khanh at 02:40, 15 November 2021

2021-11-15T02:40:03Z

Lila: /* Non-negative even numbers */

2021-10-12T20:04:05Z

Non-negative even numbers

Lila: /* Well formed formulas */

2021-10-12T20:03:43Z

Well formed formulas

Lila: /* Prime numbers */

2021-10-12T20:03:07Z

Prime numbers

Lila: /* Elementary functions */

2021-10-12T20:02:44Z

Elementary functions

Lila: /* Well formed formulas */

2021-10-12T20:02:11Z

Well formed formulas

Lila: /* Recursive Definition= */

2021-10-12T20:01:26Z

Recursive Definition=

Lila: /* Resources */

2021-10-12T19:59:29Z

Resources

Lila: /* Recursion in mathematics */

2021-10-12T19:58:28Z

Recursion in mathematics

Lila: /* Recursion in mathematics */

2021-10-12T19:57:38Z

Recursion in mathematics

@@ Line 1: / Line 1: @@
-[[File:Sierpinski triangle.svg|thumb|250px|The [[Sierpinski triangle]]—a confined recursion of triangles that form a fractal]]
+[[File:Sierpinski triangle.svg|thumb|250px|The Sierpinski triangle—a confined recursion of triangles that form a fractal]]
 ==Recursive Definition===
 In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set. Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set.
@@ Line 119: / Line 119: @@
 By induction, {{math|1=''F''(''n'') = ''G''(''n'')}} for all <math>n \in \N</math>.
-==Resources==
+== Licensing ==
-* [https://en.wikipedia.org/wiki/Recursion Recursion], Wikipedia
+Content obtained and/or adapted from:
-* [https://en.wikipedia.org/wiki/Recursive_definition Recursive definition], Wikipedia
+* [https://en.wikipedia.org/wiki/Recursion Recursion, Wikipedia] under a CC BY-SA license

@@ Line 43: / Line 43: @@
 ===Non-negative even numbers===
-The [[even number]]s can be defined as consisting of
+The even numbers can be defined as consisting of
 * 0 is in the set ''E'' of non-negative evens (basis clause),
 * For any element ''x'' in the set ''E'', ''x''&nbsp;+&nbsp;2 is in ''E'' (inductive clause),

@@ Line 49: / Line 49: @@
 ===Well formed formulas===
-It is chiefly in logic or computer programming that recursive definitions are found. For example, a [[well-formed formula]] (wff) can be defined as:
+It is chiefly in logic or computer programming that recursive definitions are found. For example, a well-formed formula (wff) can be defined as:
-#a symbol which stands for a [[proposition]] – like '''p''' means "Connor is a lawyer."
+#a symbol which stands for a proposition – like '''p''' means "Connor is a lawyer."
 #The negation symbol, followed by a wff – like '''Np''' means "It is not true that Connor is a lawyer."
-#Any of the four binary [[Logical connective|connective]]s (''C'', ''A'', ''K'', or ''E'') followed by two wffs. The symbol '''K''' means "both are true", so '''Kpq''' may mean "Connor is a lawyer, and Mary likes music."
+#Any of the four binary connectives (''C'', ''A'', ''K'', or ''E'') followed by two wffs. The symbol '''K''' means "both are true", so '''Kpq''' may mean "Connor is a lawyer, and Mary likes music."
 The value of such a recursive definition is that it can be used to determine whether any particular string of symbols is "well formed".
@@ Line 59: / Line 59: @@
 * '''NKpq''' is well formed, because it is '''N''' followed by '''Kpq''', which is in turn a wff.
 * '''KNpNq''' is '''K''' followed by '''Np''' and '''Nq'''; and '''Np''' is a wff, etc.
 ==Proofs with recursion==

@@ Line 37: / Line 37: @@
 ===Prime numbers===
-The set of [[prime number]]s can be defined as the unique set of positive integers satisfying
+The set of prime numbers can be defined as the unique set of positive integers satisfying
-* [[1 (number)|1]] is not a prime number,
+* 1 is not a prime number,
 * any other positive integer is a prime number if and only if it is not divisible by any prime number smaller than itself.
 The primality of the integer 1 is the base case; checking the primality of any larger integer ''X'' by this definition requires knowing the primality of every integer between 1 and ''X'', which is well defined by this definition. That last point can be proved by induction on ''X'', for which it is essential that the second clause says "if and only if"; if it had said just "if" the primality of for instance 4 would not be clear, and the further application of the second clause would be impossible.

@@ Line 23: / Line 23: @@
 ===Elementary functions===
-[[Addition]] is defined recursively based on counting as
+Addition is defined recursively based on counting as
 :<math>0 + a = a,</math>
 :<math>(1+n) + a = 1 + (n+a).</math>
-[[Multiplication]] is defined recursively as
+Multiplication is defined recursively as
 :<math>0 a = 0,</math>
 :<math>(1+n)a = a + na.</math>
-[[Exponentiation]] is defined recursively as
+Exponentiation is defined recursively as
 :<math>a^0 = 1,</math>
 :<math>a^{1+n} = a a^n.</math>
-[[Binomial coefficients]] can be defined recursively as
+Binomial coefficients can be defined recursively as
 :<math>\binom{a}{0} = 1,</math>
 :<math>\binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}.</math>

← Older revision		Revision as of 20:02, 12 October 2021
Line 60:		Line 60:
	* '''KNpNq''' is '''K''' followed by '''Np''' and '''Nq'''; and '''Np''' is a wff, etc.		* '''KNpNq''' is '''K''' followed by '''Np''' and '''Nq'''; and '''Np''' is a wff, etc.

		+
		+	==Proofs with recursion==
	====Example: the natural numbers====		====Example: the natural numbers====

← Older revision		Revision as of 20:01, 12 October 2021
Line 19:		Line 19:

	Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0 (or 1), and the property holds of n+1 whenever it holds of n, then the property holds of all natural numbers.		Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0 (or 1), and the property holds of n+1 whenever it holds of n, then the property holds of all natural numbers.
		+
		+	==Examples of recursive definitions==
		+
		+	===Elementary functions===
		+	[[Addition]] is defined recursively based on counting as
		+	:<math>0 + a = a,</math>
		+	:<math>(1+n) + a = 1 + (n+a).</math>
		+	[[Multiplication]] is defined recursively as
		+	:<math>0 a = 0,</math>
		+	:<math>(1+n)a = a + na.</math>
		+	[[Exponentiation]] is defined recursively as
		+	:<math>a^0 = 1,</math>
		+	:<math>a^{1+n} = a a^n.</math>
		+	[[Binomial coefficients]] can be defined recursively as
		+	:<math>\binom{a}{0} = 1,</math>
		+	:<math>\binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}.</math>
		+
		+	===Prime numbers===
		+	The set of [[prime number]]s can be defined as the unique set of positive integers satisfying
		+	* [[1 (number)\|1]] is not a prime number,
		+	* any other positive integer is a prime number if and only if it is not divisible by any prime number smaller than itself.
		+	The primality of the integer 1 is the base case; checking the primality of any larger integer ''X'' by this definition requires knowing the primality of every integer between 1 and ''X'', which is well defined by this definition. That last point can be proved by induction on ''X'', for which it is essential that the second clause says "if and only if"; if it had said just "if" the primality of for instance 4 would not be clear, and the further application of the second clause would be impossible.
		+
		+	===Non-negative even numbers===
		+	The [[even number]]s can be defined as consisting of
		+	* 0 is in the set ''E'' of non-negative evens (basis clause),
		+	* For any element ''x'' in the set ''E'', ''x'' + 2 is in ''E'' (inductive clause),
		+	* Nothing is in ''E'' unless it is obtained from the basis and inductive clauses (extremal clause).
		+
		+	===Well formed formulas===
		+	It is chiefly in logic or computer programming that recursive definitions are found. For example, a [[well-formed formula]] (wff) can be defined as:
		+	#a symbol which stands for a [[proposition]] – like '''p''' means "Connor is a lawyer."
		+	#The negation symbol, followed by a wff – like '''Np''' means "It is not true that Connor is a lawyer."
		+	#Any of the four binary [[Logical connective\|connective]]s (''C'', ''A'', ''K'', or ''E'') followed by two wffs. The symbol '''K''' means "both are true", so '''Kpq''' may mean "Connor is a lawyer, and Mary likes music."
		+
		+	The value of such a recursive definition is that it can be used to determine whether any particular string of symbols is "well formed".
		+
		+	* '''Kpq''' is well formed, because it is '''K''' followed by the atomic wffs '''p''' and '''q'''.
		+	* '''NKpq''' is well formed, because it is '''N''' followed by '''Kpq''', which is in turn a wff.
		+	* '''KNpNq''' is '''K''' followed by '''Np''' and '''Nq'''; and '''Np''' is a wff, etc.

	====Example: the natural numbers====		====Example: the natural numbers====

← Older revision		Revision as of 19:59, 12 October 2021
Line 80:		Line 80:
	==Resources==		==Resources==
	* [https://en.wikipedia.org/wiki/Recursion Recursion], Wikipedia		* [https://en.wikipedia.org/wiki/Recursion Recursion], Wikipedia
		+	* [https://en.wikipedia.org/wiki/Recursive_definition Recursive definition], Wikipedia