Editing Recursive function
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
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: | 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=== | ===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. | 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. | + | :'''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. | ||
− | '''Solution''': If | + | :'''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. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | '''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=== | ===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. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | '''Problem''': Locate a file by name on a filesystem | + | |
− | + | ||
− | '''Solution''': | + | |
− | + | ||
− | '''Example instance''': | + | |
− | : | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |