قالب وردپرس درنا توس
Home / Tips and Tricks / What is recursion in programming and how do you use it? – CloudSavvy IT

What is recursion in programming and how do you use it? – CloudSavvy IT



Shutterstock/Olga Donchuk

Recursion is an important part of functional programming that can help solve complex problems with elegant solutions. However, it is important to understand the pros and cons so that it can be done correctly.

What is recursion?

The short answer is that recursion is basically when a function calls itself, usually with some other input passed to the underlying function. It calls itself over and over until an exit condition is met, then passes the results back to the call stack, potentially modifying them as well.

The long answer is that recursion can help solve complicated problems by breaking them down into smaller subsets of the main problem. You often have data structures with nested data. Breaking this down into smaller amounts of data makes it easier to process.

For example, suppose that 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 goes through the tree leaf by leaf, inspects all the children and calculates 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 doesn’t care what sheet you call it with. He calls himself repeatedly until he hits the last leaf in the tree, which has no children. Therefore, it simply returns its own value. That value is passed to the parent sheet, which adds the child’s value to its own, and then iterated for all siblings that the child sheet has. Ultimately, the end result of the function is the total sum of all the leaves in the tree.

At some point you have to cessation case, that’s the part of the problem you know the answer to without making 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 has no 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, to calculate the factorial of a number, you must multiply it by every smaller number. You can do this very easily with recursion:

int Factorial(int n)
{
   if (n <= 1)
       return 1;
 
   return n * Factorial(n-1);
}

In this example, the halting case is when n reaches 1, where it eventually returns a value and the call stack can be collapsed.

Let’s look at a real world example. In this piece of code there is a Container class that contains multiple UI elements associated with it, as well as multiple child containers with their own elements. It should be “rendered” to a flat list of elements that can be displayed on the screen.

This is actually a different tree data structure, so the approach is similar. Except in this case, the total variable is a list, to which the element lists of each container are added.

The magic of doing recursion is that it preserves the Z order of the elements. Elements drawn after other elements appear at the top, so the container for the youngest child always appears at the top. In this scenario, I also found it useful to display overlay elements, which are added after the other elements and children have finished rendering.

The dangers of recursion

So, when should you use recursion in your code? The answer is that you should probably avoid it in most situations, especially when an iterative solution with a simple loop will get the job done.

Every time you call a function, your program allocates resources to that function. All local variables and info go to the stack, which is a Last-In, First-Out (LIFO) data structure. This means that the last function call is always removed first, like a bucket where you always remove the top element.

The problem with recursion is that it can use a nested function call for any element being processed. This results in much more overhead, as each function call needs its own set of local variables and parameters. It takes additional processing time compared to a loop-based approach.

Loops do not have this problem. After each loop iteration, the topmost element of the stack is cleared. It could handle a billion elements with the same stack.

Using too many resources with recursive function calls can result in: stack overflow, where the program can crash based on too many nested calls. This can happen with particularly large data sets, or with bad algorithms like binary or exponential recursion, which call themselves multiple times per function call.

Use recursion sparingly

Recursion is nice to have for certain problems, but there are basically no recursive solutions for problems that can’t also be solved with loops (except for nested recursion like Ackerman’s function). Even complex tree data structures can be traversed using loops and stacks. If you need to process large amounts of data or attach great importance to performance, it is better to use an iterative solution.

The other problem with recursion is that it can lead to code that is difficult for other people to understand, because it usually takes a bit of thinking before someone gets it. While it often seems like the more “elegant” solution, your job as a programmer isn’t to show off, but to write functional, readable code.

Either way, you’ll want to think about whether the problem in question is 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 look at it, I actually noticed a problem. While it worked fine, it’s written in the lazy, obvious way and as such uses way more memory than it needs. This isn’t really a problem with the small data structures it handles, but it did create a new List() for each call to the function, and appending the results of the child children. This meant that if it got a container with deeply nested children, it would keep storing the same data for no reason.

The solution in this case was to pass the recursive function a reference to an external list and append all the elements directly to it. This also meant that the Render() function in a function that handled the top-level setup for the recursive build function.

This achieves the exact same solution by adding each element in the correct order, but solves the problem that memory usage increases exponentially with each call.

Still, I’m happy with this feature as it’s quite concise and gets the job done easily. If I converted this to a solution using a loop, it would be a lot more complicated and do the exact same thing. You should weigh the pros and cons of using a recursive solution and only use it where you don’t expect serious resource usage. In this case, I don’t expect to call this function with nested containers that are hundreds of elements deep, so it’s fine to use recursion here.


For more information on this topic, see our guide to recursion.


Source link