A recursive function is a loop-like block of code in a program wherein this certain function calls on itself to perform a specific task and is rather harder to understand than those of an iterative function. As an introduction to recursion, the example below shows the simplest form of a recursive algorithm.
Using C++… (Bloodshed’s Dev-Cpp)
int num = 0;
main()
{
cout<<num<<" ";
num++;
getch();
return main();
}
As you notice, in the above code, the main() function calls on itself in the later part right before the end bracket of the function. Try to code this in C++, don’t forget to include iostream and conio.h, this would result into a never-ending running application wherein this program will print an ascending number starting from 0, increment the value of num, waits for a user key input, prints the new number, increment the value of num, wait for another user key input and so on, and so forth.
Well of course, this example already explains recursion, but, take note that it is not the usual application of a useful recursive algorithm. If you think just by understanding the example above, you’ve already understood the whole idea of recursion, then think again. Have you heard of the "quick sort algorithm", or "binary search tree algorithm", or perhaps, "towers of hanoi"? These problems are made out of recursion. But take note of this, as a programmer, I strongly believe that for every recursive function, there is always an iterative equivalent and is much faster but harder and longer to write. In the programming world, one would always face the dilemma between speed and maintainability of codes. I’d like to stress, for complex algorithms, recursion is often much more maintainable but slower in performance, while iteration produces faster performance but much more difficult to maintain. Simply because, recursion may already result into a desired function but would only be written in only a small amount of lines of codes, while an iterative equivalent would most likely should be written in fewer lines. So, if ever you’d like to decide to write a recursive function than an iteration, you should be able to understand first how recursion works.
Programmers have been explaining, for every recursive function call (the part or the line where the function calls on itself), whatever the result of that certain call is independent from the current procedure itself. Which means, there just came a chance wherein a function which produces a specific task is also in need of the result of the very same function itself.
For example, a function has a specific task, wherein it splits a string into an array of string. Somewhere inside the function, by chance, it would also need a function which performs splitting of a string into an array of string. So, rather than calling another foreign function to do the job, it would just necessarily call itself instead since the purpose of this function is to split a string into an array of string. Got the idea?
Before, I had a hard time understanding recursion, not until I learned Binary Tree, specifically the Binary Search Tree (BST). Since I can explain BST better for recursion, then let’s understand BST first.
BST is the special technique used by programmers to quickly search for a certain item inside a list of data. Of course, for manageability purposes, a list of data inside a Binary Tree must be arranged in a sorted manner. So later, it won’t be hard to search for an item. Here’s where a BST comes in. Suppose we have a list of 1 million items, considering the data are already sorted, would you search for a certain item by starting from the very beginning or from the end? Suppose you’d start from the first item, what if the actual location of the searched item is just 5 items from the end list? Or if you’d start from the end, and the actual location is at the 6th Rank? Mind you, it would take the program to iterate almost a million times just to search for that certain data, which would rather result into a very slow performance.
To eliminate this undesirable result, programmers created a faster way to search using a recursive algorithm most commonly known as the "divide and conquer algorithm". Introducing, Binary Search Tree: BST starts it’s search from the midpoint of a list of items. The midpoint can be calculated by adding the value of the starting index to the value of the ending index divided by 2 [ in the form ((LowerBound + UpperBound) / 2) ]. For example we are searching number 40 in the list below…
1 3 4 5 8 9 13 14 18 19 20 26 35 36 40 41 45
In the list of numbers above, we assume that the LowerBound index is 0, and the UpperBound index is 16. So we find the midpoint by adding 0 and 16, since there are 17 items in the list, divide by 2. The midpoint is 8, which is the item "18" (Take note that the list starts at index 0, so index 8 should be at the 9th item). Then following the BST rule, we would check if the midpoint is the number we are searching for. If it is the right number then return the number, if not, then we continue the searching process.
Now what do we do after we found out that the midpoint is not yet the number we are looking for? We will now divide the task. Since we know that the list is sorted, have you noticed that all numbers to left of the midpoint are actually numbers less than this midpoint. And all numbers to its right are greater. We would then again want to search for the right number by taking all the numbers to the left as a new list of numbers, and the numbers to the right as another list of numbers. Find each midpoint, divide again the list into two until the midpoint is exactly the number we are looking for. This is where the recursive function is used. Since our function’s purpose is to check whether the midpoint of the list is the number we are searching for, and we came to a point wherein we need a certain function to search for the midpoint of a list and check whether this is the number we are searching for, we will then call the function itself.
1 3 4 5 8 9 13 14 18 19 20 26 35 36 40 41 45
Notice above, the numbers in red becomes the new list of numbers wherein we’d search again for the midpoint and check whether this midpoint is the number we are looking for, and same for those new list in blue. And the current midpoint, which is "18", won’t be used anymore as part in the new list to be searched. Therefore, the new list would be…
1 3 4 5 8 9 13 14 … We find the midpoint using the same formula as mentioned above…
and…
19 20 26 35 36 40 41 45 … Find also the midpoint and check if it’s the number we are looking for…
If the midpoint for each list is once again found, and it showed that the midpoint is not the number we are looking for, repeat the process of dividing the list into 2 until we find the number we are searching for.
Have you tried to visualize what the output would be? I hope this is a better way of explaining recursion. Just remember, upon handling recursive functions, you must consider 3 things: First, how would you begin the recursion. Second, what are the contents of the function. Lastly, what could trigger for the function to end. Search for different examples of recursion. You would notice a starting statement on an "If… If Else" Learn why it should appear. But just a clue, this "If statement" handles the recursion on when it should end its process.
I have written a function in Visual Basic which draws a "Crack-Like Image" on a Picture Box, rather useful as a tool for an Image Editor Application. If you are a VB Programmer, try to download my submission on PSCode right in this link… Paint Tool - Using Recursive Algorithm.
