RELATED: What Is Recursion in Programming, and How Do You Use It?
What Is Recursion?
The short answer is that Recursion is basically whenever a function calls itself, usually with a different input passed to the child function. It calls itself over and over until an exit condition is reached, and then passes the results back up the call stack, potentially modifying them on the way up as well.
The long answer is that recursion can help solve complicated problems by breaking them down into smaller subsets of the main problem. Often, you will have data structures containing nested data. Breaking this down into smaller amounts of data will make this easier to process.
For example, say each leaf in the tree had a value associated with it, and we wanted to find the sum of all the values. We could do that with a function like the following, which traverses the tree leaf by leaf, inspecting all the children and calculating the total.
This works because CountAllLeaves doesn’t care about which Leaf you call it with. It repeatedly calls itself until it hits the final leaf in the tree, which doesn’t have any children. Because of that, it simply returns its own value. That value is passed to the parent leaf, which adds the child’s value to its own, and then repeats for all the siblings that child leaf has. In the end, the final result of the function will be the total sum of all the leaves in the tree.
At some point, you must reach the halting case, which is the piece of the problem that you know the answer to without making any more recursive calls. Otherwise, the function would loop forever, causing the program to crash. In this case, the halting case is when the function reaches a leaf that doesn’t have any children.
It doesn’t have to be about nested data structures like trees. You can write recursive functions around any type of problem. For example, calculating the factorial of a number involves multiplying it by each number smaller than it. You can do this very easily with recursion:
In this example, the halting case is when n reaches 1, where it finally returns a value and the call stack can be collapsed.
Lets look at a real-world example. In this bit of code, there is a Container class which contains multiple UI elements attached to it, as well as multiple child containers with their own elements. It must be “rendered” out to a flat list of elements which can be shown on screen.
This is basically another tree data structure, so the approach is similar. Except, in this case, the total variable is a list, which gets the Elements lists of each Container appended to it.
The magic of doing it using recursion is that it preserves the Z-order of the elements. Elements drawn after other elements go on top, so the youngest child container will always display on top. In this scenario, I also found it useful to display overlay elements, which get added after the other elements and children finish rendering.
The Dangers Of Recursion
So, when should you use recursion in your code? The answer is you should actually probably avoid it in most situations, especially when an iterative solution using a simple loop will get the job done.
Every time you call a function, your program allocates resources towards that function. All local variables and info go onto the stack, which is a Last-In, First-Out (LIFO) data structure. This means the latest function call is always the first to be removed, like a bucket where you always remove the top element.
The problem with recursion is that it can use a nested function call for each element being processed. This results in a lot more overhead, as each function call needs its own set of local variables and parameters. It will take extra processing time compared to a loop based approach.
Loops don’t have this problem. After each loop iteration, the stack will have the top element cleared off. It could process a billion elements using the same stack.
If you use too many resources with recursive function calls, it can result in stack overflow, where the program can crash just based on too many nested calls. This can happen with particularly large data sets, or with poor algorithms like binary or exponential recursion, which call themselves multiple times per function call.
Use Recursion Sparingly
Recursion is a nice thing to have for certain problems, but there are basically no recursive solutions to problems that can’t also be solved using loops (except for nested recursion like Ackerman’s function). Even complicated tree data structures can be traversed using loops and stacks. If you need to handle large amounts of data, or care a lot about performance, you might be better off using an iterative solution.
The other problem with recursion is that it can lead to code that is difficult for other people to understand, as it usually takes a bit of head scratching before someone gets it. While it often seems like the more “elegant” solution, your job as a programmer is not to show off, and is instead to write functional, readable code.
In any case, you’ll want to think about whether or not the problem at hand would be better off using a loop. Recursion should be your last resort for problems that would be much more complicated without it. In fact, in my entire 40,000 lines of source code, I only had one example of recursion for this article.
And, after a second glance at it, I actually noticed a problem. While it worked fine, it was written the lazy, obvious way, and as such is using a lot more memory than it needs. This isn’t really a problem with the small data structures it’s handling, but it was creating a new List
The solution in this case was to pass the recursive function a reference to an external list, and add all the elements to it directly. This also involved changing the Render() function into a function that handled the top-level setup for the recursive build function.
This accomplishes exactly the same solution of adding each element in the proper order, but fixes the problem of memory usage going up exponentially with each call.
Still, I’m happy with this function as it’s quite concise and gets the job done easily. If I was to convert this to a solution using a loop, it would be a lot more complicated and do the exact same thing. You will need to weigh the pros and cons of using a recursive solution, and only use them where you’re not expecting serious resource usage. In this case, I’m not expecting to be calling this function with nested containers that are hundreds of elements deep, so using recursion here is fine.
For more info on this topic, see our guide to Recursion.
