|
|
|
|
| I'm no algorithm buff, so I really can't do justice to the full topic of recursion. However, I'd be doing you a great disservice if I didn't make some mention of it. Recursion, in simplest terms, happens when a method that calls itself. This is considered by some to be the most compelling and powerful example of code reuse. Here's a basic example: private static int StepInteger(int number, int step) { if( step > 1 ) { number = number * 2; return StepInteger(number, --step); } else { return number; } } Most recursive methods have two easily identifiable features: the first is that the method contains a conditional call to itself. The second is that the method performs operations on some data, and then passes the modified data into its next call to itself. This usually includes a "control" counter that is decremented with each recursive call (in this example, the "control" counter is called "step"). The recursive call is only made as long as a certain condition is true. The above method essentially doubles the value of [number], [step] number of times. If you passed in 5 and 3 as your parameters, the final result would be 20... that's 5 doubled 3 times. Each time the method calls itself, the value of "step" is checked. If "step" is still more than 1, the value of number is doubled, and the method calls itself with a step value that has been reduced by 1. Eventually, "step" will fall below 1, the method will stop calling itself, and the final value of the number you were doubling will be returned to the code that originally called the method. Obviously, the above example is a pretty tame use for recursion. You could just write a "for" loop that would effectively do the same thing. In fact, most problems that can be solved by recursion are also solvable with loops. However, recursion offers the benefits of a method call (encapsulating a block of code into one isolated unit), which gives it an advantage over ordinary loops in some circumstances. As with any method, you can have as many parameters in the recursive function as you want, and you can also have several different possible recursive calls, based on the status of a certain value (instead of the "two-dimensional" if/else recursive call shown above). There's a few things to watch out for with recursion. For one thing, if your "if" statement always evaluates to "true", your method will get stuck in an endless loop, calling itself forever. Make sure that something changes every time the method calls itself, even if it's just an arbitrary control variable like the one I used above. By the same token, after your method changes the actual values you're operating on, make sure that you pass the new values into the next recursive call, and not the original ones! Also don't forget that recursion relies on a what could end up being a fairly "deep" series of method calls. If the method calls get deep enough, you'll get a stack overflow error. Recursion can be tricky to program. Because you have a single block of code that's getting called hundreds of times, with different values, recursive methods can be fiendishly difficult to debug when something goes wrong. And it may not always be obvious where your mistake is. Still, recursion is an extremely powerful tool in the hands of someone who knows how wield it, so it's worth dabbling in, at least to the point where you can write and understand your own recursive function. Another recursion example has been provided in the code sample below. As stated, however, neither of these examples really do recursion justice. They're simply here to get you thinking about the possibilities of a method that can call itself. If you want a really famous example of recursion, google around for "Towers of Hanoi", and look for a C# implementation of it. using System; namespace E_Recursion { class Class1 { static readonly string ln = Environment.NewLine; [STAThread] static void Main(string[] args) { string oldText = "Recursion"; string newText = StepText(oldText, 3); Console.WriteLine(newText); Console.WriteLine(ln + StepText("More Recursion", 7)); // If we really wanted to be cool (insert ironic grin here), // we could create a method that recursively calls our recursive // method, so that StepText is kicked off with a decrementing // number each time! PromptForExit(); } // All this example really does is print a decreasing number // of characters on a given number of lines. However, it should // illustrate the possibilities of a method that can call itself, // and make different decisions based on the parameters each time. static string StepText(string text, int step) { string ret = text + ln; for(int i = 0; i < step; ++i) ret += i; // Have the method call itself, but only under specific // conditions (if the method calls itself explicitly, // you'll be stuck in a loop, and ultimately crash // from a stack overflow) if( step > 1 ) ret = StepText(ret, --step); return ret; } static void PromptForExit() { Console.Write(ln + "Program complete! Hit enter to exit..."); Console.ReadLine(); } } } |
|
|