What Is Recursion In Programming And How To Use It
What Is Recursion in Programming, and How Do You Use It?
Recursion is a critical component of functional programming because it enables the solution of complex problems in an elegant manner. However, it is critical to understand the benefits and drawbacks in order to complete the task correctly.
What Exactly Is Recursion?
In a nutshell, recursion occurs whenever a function calls itself, typically with a different input parameter passed to the child function. It repeatedly calls itself until an exit condition is reached, and then returns the results up the call stack, possibly modifying them along the way.
The long answer is that recursion can assist in the resolution of complex problems by decomposing them into smaller subsets of the original problem. Frequently, you will encounter data structures that contain nested data. This will be easier to process if the data is broken down into smaller chunks.
For instance, suppose each leaf in the tree had a value and we desired to find the sum of all the values. That could be accomplished with the following function, which traverses the tree leaf by leaf, inspecting each child and calculating the total.
int CountAllLeaves(Leaf currentLeaf)
{
// Start with the current value
int Total = currentLeaf.value;
// Add any children to the value, if any
foreach(Leaf childLeaf in currentLeaf.children)
{
Total = Total + CountAllLeaves(childLeaf);
}
return Total;
}
This works because CountAllLeaves is unconcerned with the Leaf name. It repeatedly calls itself until it reaches the tree's final leaf, which has no children. As a result, it simply returns the value itself. This value is passed to the parent leaf, which then adds the child's value to its own and repeats for all of the child leaf's siblings. Finally, the function's output will be the sum of all the leaves in the tree.
At some point, you must reach the halting case, which is the section of the problem for which you know the solution without further recursive calls. Otherwise, the function would continue to loop indefinitely, resulting in the program's crash. In this case, the function terminates when it reaches a leaf that has no children.
It is not necessary to discuss nested data structures such as trees. Recursive functions can be written to solve any type of problem. Calculating the factorial of a number, for example, entails multiplying it by each smaller number. This is extremely simple to accomplish using recursion:
int Factorial(int n)
{
if (n <= 1)
return 1;
return n * Factorial(n-1);
}
In this example, the halting case occurs when n equals 1, at which point the call stack can be collapsed.
Consider the following real-world scenario. This section of code contains a Container class that is attached to multiple UI elements and has multiple child containers with their own elements. It must be "rendered" into a flat list of elements suitable for display on the screen.
Due to the fact that this is essentially another tree data structure, the approach is similar. Except that in this case, the total variable is a list that is appended with the Elements lists of each Container.
The magic of recursion is that it preserves the elements' Z-order. Elements that are drawn after other elements are displayed on top, ensuring that the youngest child container is always displayed first. Additionally, I found it useful to display overlay elements in this scenario, which are added after the other elements and children have rendered.
The Dangers Of Recursion
So when is it appropriate to use recursion in your code? The answer is that you should probably avoid it in the majority of cases, particularly when an iterative solution utilizing a simple loop will suffice.
Each time you invoke a function, your program allocates resources to it. The stack is a Last-In, First-Out (LIFO) data structure that stores all local variables and information. This means that the most recent function call is always the first to be removed, similar to a bucket where the top element is always removed.
The issue with recursion is that it can use nested function calls to process each element. This adds significant overhead because each function call requires its own set of local variables and parameters. It will require more processing time than a loop-based approach.
This is not an issue with loops. After each loop iteration, the stack's top element is removed. It is capable of processing one billion elements with the same stack.
If you use too many resources with recursive function calls, you risk a stack overflow, which can cause the program to crash due to the excessive number of nested calls. This can occur when dealing with extremely large data sets or when using inefficient algorithms such as binary or exponential recursion, which call themselves multiple times during each function call.
Use Recursion Sparingly
While recursion is advantageous for certain problems, there are virtually no recursive solutions that cannot also be solved using loops (with the exception of nested recursion such as Ackerman's function). Loops and stacks can be used to traverse even the most complex tree data structures. If you need to handle a large amount of data or are concerned about performance, an iterative solution may be preferable.
The other issue with recursion is that it can result in code that is difficult to understand for others, as it typically requires some head scratching before someone grasps it. While this may appear to be the more "elegant" solution, your job as a programmer is to write functional, readable code.
In any case, you'll want to consider whether or not a loop would be a better fit for the problem at hand. Recursion should be used as a last resort when confronted with problems that would be significantly more complicated without it.
And, upon a second glance, I noticed a flaw. While it worked fine, it was written in a lazy, obvious manner and thus consumes significantly more memory than necessary. This isn't really a problem given the small data structures it's handling, but it was creating a new ListCuiElement>() for each call of the function and appending the results of the children below. This meant that if it was given a container with deeply nested children, it would unnecessarily store the same data.
In this case, the solution was to pass the recursive function a reference to an external list and directly add all the elements to it. This also required rewriting the Render() function as a top-level setup function for the recursive build function.
This achieves the same result as adding each element in the correct order, but avoids the issue of memory usage increasing exponentially with each call.
Courses and Certification
Python 3 Course and Certificate
JAVA Programming Course and Certificate
Computer Programming Course and Certificate
Extreme Programming Course and Certificate
Functional Programming Course and Certificate
Programming Methodologies Course and Certificate
