As Recursion is a fundamental concept in programming and computer science, you may have come across it before. In fact, it's so important and useful that almost all modern programming languages – including Go – support it. And if you're looking for a new role, then recursion is also pretty common in technical interviews for software developer positions.
In this tutorial, we'll learn what recursion is and its difference with iterative solutions. Then, we'll also talk about recursion in Golang, with an example of a recursive function to find factorials.
Simply put, recursion is when a function calls itself. It's a powerful technique for breaking down complex problems into smaller, easier-to-manage ones.
A recursive method solves a problem by calling itself to work on a smaller version of the problem. This is called the recursion step. Each recursion step can result in many more such recursive calls.
Some problems are much easier to solve using recursion. In modern computing, here are a few common applications of recursion:
There are also well-known classic algorithms that use recursion. Some examples that you may already know:
Recursion is fundamental to computing. By learning how to use recursion, you can break complex computing problems down into smaller pieces – aka, you'll make it easier for yourself.
Even if you don't use recursion in your everyday work, it's still worth learning it. Why? Understanding its concepts and applications can improve your algorithmic thinking. Besides, the topic is often asked during technical job interviews. Who knows, knowing how recursion works will help you get the job you want 😉
A recursive function performs a task by calling itself to perform simpler subtasks. It's referred to as the recursive case. At some point, the function needs to end calling itself. This condition is called the base case. And in order to reach the base case, the recursive case must move forward the base case.
You can write the body of a recursive function using the following format:
Don't worry if you're still unclear about how to write a recursive function. In the following section, we'll look at an example in Go.
The symbol for factorial is an exclamation mark (!). And the result of n! (or "n factorial") is the product of all the numbers between 1 and n, where n must always be positive values. Please note that 0! is a special case, and the result of 0! is 1.
Example of factorial calculations:
Now, let's see a program in Go.
The below code snippet contains a Factorial function (line 5-11) that implements recursion. Notice that the function calls itself in line 10. It takes a parameter (n), which is a number, then returns the factorial of that number.
The main method defines an integer with a value of 5 (n = 5). Then, it calculates the factorial of 5 and stores it in a variable called fac, and prints the result.
If you run the program, you'll see an output as the following shows:
The visualisation of factorial function with n=5 will look like the following:
When you call a recursive function, each recursive call creates an additional stack frame on the stack until it reaches the base case. Once the code reaches the base case, the stack starts to unwind as each function on top of it returns its results.
It's important to note that any recursive functions can be solved using iterative loops as well. So, while discussing recursion, some of the basic questions that come to mind are often:
Well, recursive code is generally shorter than iterative code. It's also more elegant (but that's just our personal opinion). For a newcomer, though, it can be hard to understand and implement.
This is an example version of the Factorial function using iteration:
In terms of efficiency, iterative solutions are generally more efficient than recursive solutions. That's because recursion requires more memory — each recursive call consumes extra space on the stack frame. You'll get the potential of stack overflow problems if the recursion is too deep or infinite.
Yes, of course.
It's no surprise that some programmers will tell you never to use recursion. However, in some situations, using recursion can be beneficial. And you can avoid its pitfalls by handling them properly.
Different programming languages will have different ways of handling the problems.
In Golang, stacks grow as needed. It makes the effective recursion limits relatively large. The initial setting is 1 GB on 64-bit systems and 250 MB on 32-bit systems. The default can be changed by SetMaxStack in the runtime/debug package.
Here's an example:
Let's say that the development time is an expensive cost for your employer. You're facing a complex problem and can quickly come up with a recursive solution rather than an iterating one. In this case, you'd serve your employer well.
You'll also need to consider the memory usage that your program will consume. Otherwise, the stack overflow error might appear.
After reading this tutorial, you should have knowledge of the basics of recursion. You should also be able to write and manage a recursive function in Go and understand the difference between recursion and iterative solutions.
We hope that you will begin to see opportunities where thinking recursively would help you solve certain complex computational problems you come across. Furthermore, we hope that you will find this information helpful for your future job interview. If you're looking for a new role in tech where you might be able to use these new skills, look no further! Sign up to hackajob here and get matched with your dream role in just weeks. Good luck!
Like what you've read or want more like this? Let us know! Email us here or DM us: Twitter, LinkedIn, Facebook, we'd love to hear from you.