Recursive function - Revision history

Brian at 02:05, 14 February 2012

2012-02-14T02:05:33Z

Brian: /* Statement */

2012-01-04T08:32:58Z

‎Statement

Brian at 23:48, 29 July 2011

2011-07-29T23:48:07Z

Show changes

Brian: not done yet

2011-07-29T20:24:26Z

not done yet

Brian at 19:36, 28 June 2011

2011-06-28T19:36:36Z

Brian: Created page with "'''Recursion''' is the property exhibited by entities that are defined in terms of themselves, that is, ''recur'' in themselves. In computer science, the most important recursive..."

2011-06-26T02:35:33Z

Created page with "'''Recursion''' is the property exhibited by entities that are defined in terms of themselves, that is, ''recur'' in themselves. In computer science, the most important recursive..."

New page

'''Recursion''' is the property exhibited by entities that are defined in terms of themselves, that is, ''recur'' in themselves. In computer science, the most important recursive entities are ''recursively defined functions''. Mathematical functions are usually thought of as sets of ordered pairs, the first element in the pair from the domain, the second from the range, and, hence, a function cannot be intrinsically recursive. However, functions in computer programs are instead defined in a form that allows computers to evaluate them (efficiently, it is hoped), and the definition of a function in a computer program may reference the function itself. Such a function, that occurs in its own definition, is said to be ''recursively defined'', and, with the understanding that we are speaking of the definition of a function rather than its abstract mathematical essence, we will refer to them simply as '''recursive functions'''. The term '''recursion''' is then defined also as the process of evaluating recursive functions, and, by extension, the formulation of [[algorithms]] in terms of recursive functions.

===Example===
Let <math>F(n)</math> denote the <math>n</math><sup>th</sup> Fibonacci number, where <math>n</math> is a natural number and <math>F(1) = F(2) = 1</math>. We may define <math>F</math> as a function, as follows:
:<math>F(x) =
\begin{cases}
1 & \text{if }x = 1\text{ or }x = 2 \\
F(x-1) + F(x-2) & \text{otherwise}
\end{cases}</math>

← Older revision		Revision as of 02:05, 14 February 2012
Line 169:		Line 169:
	print "File not found"		print "File not found"
	</syntaxhighlight>		</syntaxhighlight>
		+
		+	[[Category:Incomplete]]

@@ Line 59: / Line 59: @@
 Recursion is a powerful tool for solving problems, but it is not always obvious how to approach a problem recursively. The general principle, often called '''divide and conquer''', is as follows:
-<div style="border: 1px solid #ccf; width: 60%; padding: 5px; margin-left:auto; margin-right:auto">Identify instances of your problem that are so small or simple that they are trivial. Determine how to break a large or complex instance into one or more smaller or simpler instances so that the solution to the latter can be used to determine a solution to the former. By repeating this process enough times, it is possible to solve any instance, no matter how large, by reducing it to trivial pieces.</div><!-- todo: move this styling to a template, to separate it from content -->
+{{ImportantConceptBox|Identify instances of your problem that are so small or simple that they are trivial. Determine how to break a large or complex instance into one or more smaller or simpler instances so that the solution to the latter can be used to determine a solution to the former. By repeating this process enough times, it is possible to solve any instance, no matter how large, by reducing it to trivial pieces.}}
 ===Non-computer science examples===

← Older revision		Revision as of 20:24, 29 July 2011
Line 54:		Line 54:
	</syntaxhighlight>		</syntaxhighlight>
	''(Note that function names are not allowed to start with uppercase letters in Haskell.)''		''(Note that function names are not allowed to start with uppercase letters in Haskell.)''
		+
		+	==Philosophy==
		+	===Statement===
		+	Recursion is a powerful tool for solving problems, but it is not always obvious how to approach a problem recursively. The general principle, often called '''divide and conquer''', is as follows:
		+
		+	<div style="border: 1px solid #ccf; width: 60%; padding: 5px; margin-left:auto; margin-right:auto">Identify instances of your problem that are so small or simple that they are trivial. Determine how to break a large or complex instance into one or more smaller or simpler instances so that the solution to the latter can be used to determine a solution to the former. By repeating this process enough times, it is possible to solve any instance, no matter how large, by reducing it to trivial pieces.</div><!-- todo: move this styling to a template, to separate it from content -->
		+
		+	===Non-computer science examples===
		+	This philosophy is not restricted to computer science. Below we give some examples from other fields that may assist the reader in internalizing the divide and conquer philosophy and appreciating its ubiquity. When the solution to an instance requires the solutions to simpler instances, those simpler instances will be indented an additional level to show this relationship.
		+
		+	:'''Problem''': Climb a ladder. The generic form of this problem is ''Be at the top of the ladder''. The instance is where you already are. Hence, climbing from the bottom to the top and climbing from the middle to the top are both the same problem, but different instances of it.
		+	:'''Solution''': If you are already at the top, this is a trivial instance; you don't actually have to do anything. If you are not at the top, suppose there are <math>x</math> rungs remaining, where <math>x > 0</math>. Notice that the problem would be easier to solve if there were only <math>x-1</math> rungs separating you from the top of the ladder. So climb up one rung; this will reduce the instance at hand to an easier one. Repeat as necessary.
		+	:'''Example instance''':
		+	::You are 4 rungs away from the top of the ladder. The instance would become simpler if you were only 3 rungs away from the top, so climb up one rung.
		+	:::You are 3 rungs away from the top of the ladder. The instance would become simpler if you were only 2 rungs away from the top, so climb up one rung.
		+	::::You are 2 rungs away from the top of the ladder. The instance would become simpler if you were only 1 rung away from the top, so climb up one rung.
		+	:::::You are 1 rung away from the top of the ladder. The instance would become simpler if you were only 0 rungs away from the top, so climb up one rung.
		+	::::::You are at the top of the ladder. Congratulations! You've solved the problem.
		+
		+	:'''Problem''': Differentiate a function with respect to <math>x</math>. The generic form of this problem is ''Differentiate with respect to <math>x</math>''. The instance is the specific function you want to differentiate.
		+	:'''Solution''': If the function to be differentiated is a power of <math>x</math>, a constant, or a standard function of <math>x</math> (for example, <math>\sin x</math>), this is a trivial instance; you can simply use the power rule or look up the derivative in your calculus textbook. Otherwise, find the last step in computing the function; it may be addition, subtraction, multiplication, division, or a function application. Then use the sum rule, difference rule, product rule, quotient rule, or chain rule, as appropriate, on the subexpression(s), which is/are necessarily simpler than the original function. By applying these rules enough times, any elementary function can be differentiated.
		+	:'''Example instance''':
		+	::We wish to differentiate <math>\log x + e^{x^2/2}</math>. This is a complex instance. The lowest-precedence operation is the addition, so we will use the sum rule; hence, <math>\frac{d}{dx} \left(\log x + e^{x^2/2}\right) = \frac{d}{dx} \log x + \frac{d}{dx} e^{x^2/2}</math>. Each of the two derivatives on the right side is a simpler instance of this problem.
		+	:::We wish to differentiate <math>\log x</math>. This is a trivial instance, since the textbook will tell you that <math>\frac{d}{dx} \log x = 1/x</math>.
		+	:::We wish to differentiate <math>e^{x^2/2}</math>. The lowest-precedence operation is the exponential; it is done last. So we will use the chain rule, hence, <math>\frac{d}{dx} e^{x^2/2} = \left(\lambda x.\frac{d}{dx}e^x\right)\frac{x^2}{2} \frac{d}{dx} \frac{x^2}{2}</math>.
		+	::::We wish to differentiate <math>e^x</math>. This is a trivial instance; the textbook indicates that its derivative is <math>e^x</math>.
		+	::::We wish to differentiate <math>x^2/2</math>. This is a complex instance; we use the rule <math>\frac{d}{dx} kf(x) = k\frac{d}{dx}f(x)</math>, where <math>k</math> is a constant. Thus, <math>\frac{d}{dx} x^2/2 = \frac{1}{2} \frac{d}{dx}x^2</math>.
		+	:::::We wish to differentiate <math>x^2</math>. This is a trivial instance; the power rule gives its derivative as <math>2x</math>.
		+	::::Therefore, the derivative of <math>x^2/2</math> is <math>\frac{1}{2}(2x) = x</math>.
		+	:::Therefore, the derivative of <math>e^{x^2/2}</math> is <math>\left(\lambda x.e^x\right)\frac{x^2}{2}\cdot x = xe^{x^2/2}</math>.
		+	::Therefore, the derivative of <math>\log x + e^{x^2/2}</math> is <math>1/x + xe^{x^2/2}</math>. Congratulations! You've solved the problem.
		+
		+	:'''Problem''': Obtain a certain item. The generic form of this problem is ''Obtain''. The instance is the specific item you wish to obtain.
		+	:'''Solution''': If you already have the item, then you don't need to do anything; this is a trivial instance. If the item is commercially available and you wouldn't mind buying it, then simply do so; this is also a trivial instance. Otherwise, build it yourself. Identify simpler components of which the item is composed. Obtaining these components comprises easier instances of the given problem. After obtaining the required components, assemble them into the item desired.
		+	:'''Example instance''':
		+	::You live on a farm and want to prepare a rack of ribs for dinner. This is a complex instance. To solve it, you will have to first obtain the ribs and the barbecue sauce.
		+	:::You wish to obtain a rack of ribs. This is a complex instance; you will need need to slaughter and butcher a pig.
		+	::::You wish to obtain a pig. You don't raise pigs on your farm, but your neighbour raises pigs. This is a trivial instance, as you can simply buy a pig from your neighbour.
		+	:::You have obtained a pig. Now slaughter and butcher it. You have obtained a rack of ribs.
		+	:::You wish to obtain barbecue sauce. Unfortunately, you don't have any left, and your neighbour doesn't either, and it's a holiday, so the market is closed. This is a complex instance. You look in your cookbook, and find a recipe for barbecue sauce consisting of ketchup, sugar, and vinegar. You will need to obtain these and mix them.
		+	::::You wish to obtain ketchup. You already have ketchup, so this is a trivial instance.
		+	::::You wish to obtain sugar. You already have sugar, so this is a trivial instance.
		+	::::You wish to obtain vinegar. You already have vinegar, so this is a trivial instance.
		+	:::Having obtained ketchup, sugar, and vinegar, you mix them in the correct ratios, thereby obtaining barbecue sauce.
		+	::Having obtained ribs and barbecue sauce, you apply the sauce to the ribs, apply heat, and then apply more sauce. Congratulations! You have obtained a dish of ribs, ready to enjoy.
		+
		+	===Examples from computer science===
		+	:'''Problem''': Locate a file by name on a filesystem. The problem here is ''find''; the instance consists of the filename of the file we wish to find, and the directory in which we expect to find it.
		+	:'''Solution''': Locate all files in the top level of the given directory. If one of these is the desired file, this is a trivial instance; we have found the file and we are done. Otherwise, it is a complex instance. Locate all directories in the top level of the given directory. Recursively attempt to locate the file in each one of these directories.
		+	:'''Example instance''':
		+	::Locate the file <code>apache2.conf</code> somewhere under the root directory of a UNIX system.

@@ Line 1: / Line 1: @@
-'''Recursion''' is the property exhibited by entities that are defined in terms of themselves, that is, ''recur'' in themselves. In computer science, the most important recursive entities are ''recursively defined functions''. Mathematical functions are usually thought of as sets of ordered pairs, the first element in the pair from the domain, the second from the range, and, hence, a function cannot be intrinsically recursive. However, functions in computer programs are instead defined in a form that allows computers to evaluate them (efficiently, it is hoped), and the definition of a function in a computer program may reference the function itself. Such a function, that occurs in its own definition, is said to be ''recursively defined'', and, with the understanding that we are speaking of the definition of a function rather than its abstract mathematical essence, we will refer to them simply as '''recursive functions'''. The term '''recursion''' is then defined also as the process of evaluating recursive functions, and, by extension, the formulation of [[algorithms]] in terms of recursive functions.
+'''Recursion''' is the property exhibited by entities that are defined in terms of themselves, that is, ''recur'' in themselves. In computer science, the most important recursive entities are ''recursively defined functions''. Mathematical functions are usually thought of as sets of ordered pairs, the first element in the pair from the domain, the second from the range, and, hence, a function cannot be intrinsically recursive. However, functions in computer programs are instead defined in a form that allows computers to evaluate them (efficiently, it is hoped), and the definition of a function in a computer program may reference the function itself. Such a function, that occurs in its own definition, is said to be ''recursively defined'', and, with the understanding that we are speaking of the definition of a function rather than its abstract mathematical essence, we will refer to them simply as '''recursive functions'''. The term '''recursion''' is then defined also as the process of evaluating recursive functions, and, by extension, the formulation of [[algorithm]]s in terms of recursive functions.
-===Example===
+==Notation==
-Let <math>F(n)</math> denote the <math>n</math><sup>th</sup> Fibonacci number, where <math>n</math> is a natural number and <math>F(1) = F(2) = 1</math>. We may define <math>F</math> as a function, as follows:
+===In mathematics===
 :<math>F(x) =
 \begin{cases}
@@ Line 8: / Line 25: @@
 F(x-1) + F(x-2) & \text{otherwise}
 \end{cases}</math>
-<!-- unfinished -->
+'''Haskell''':