This article was written for and published by Gopher Academy
I was looking at a code sample that showed a recursive function in Go and the writer was very quick to state how Go does not optimize for recursion, even if tail calls are explicit. I had no idea what a tail call was and I really wanted to understand what he meant by Go was not optimized for recursion. I didn’t know recursion could be optimized.For those who don’t know what recursion is, put simply, it is when a function calls itself. Why would we ever write a function that would call itself? Recursion is great for algorithms that perform operations on data that can benefit from using a stack, FILO (First In Last Out). It can be faster than using loops and can make your code much simpler.Performing math operations where the result of a calculation is used in the next calculation is a classic example where recursion shines. As with all recursion, you must have an anchor that eventually causes the function to stop calling itself and return. If not, you have an endless loop that eventually will cause a panic because you will run out of memory.Why would you run out of memory? In a traditional C program, stack memory is used to handle all the coming and going of function calls. The stack is pre-allocated memory and very fast to use. Look at the following diagram:
http://golang.org/src/pkg/runtime/stack.cWhen we use recursion we need to be aware that the stack is going to grow until we finally hit our anchor and begin to shrink the stack back down. When we say that Go does not optimize for recursion, we are talking about the fact that Go does not attempt to look at our recursive functions and find ways to minimize stack growth. This is where tail calls come in.Before we talk more about tail calls and how they can help optimize recursive functions, let’s begin with a simple recursive function:
Get your team up to date with best practices & customized curriculum.
We help you evaluate your architecture, design, structure, tech-debt and human capital.
Learn at your own pace!
Special offers on upcoming training events & our latest blog posts.
Valid email required.
Submit failed. Try again or message us directly at email@example.com.
Check your email for confirmation.
We've built our reputation as educators and bring that mentality to every project. When you partner with us, your team will learn best practices and grow along the way.
Years in Business
Please fill out the form below, and we'll get back to you soon.
Check your email for confirmation of your sent message. We'll get back to you shortly.
Ardan Labs Copyrights © 2023