In the last post, we talked about some of the basic function types and features in Go. In this post, we are going to discuss recursion in Go and recursion in general. Recursion can be a confusing concept at first. Fortunately, recursion in Go is very straight forward. 

Recursive Functions

recursive-function

A recursive function is a function that makes a call to itself inside of itself. Recursion is very strong for certain types of algorithms. Recursive functions can be much more efficient then loops in some cases. Let’s look at an example of recursion with Go.

In this simple program, we have a recursive function which will print out an integer decremented by one until it is less than zero. When the value is less than zero, the function just breaks out of the recursion. To do this, we use an empty return statement. We can rewrite this program with a for-loop.

In this case, our programs will have identical behavior and there will be no real difference in performance at this scale. Even if we call an argument of one hundred thousand or one million, we won’t really see any differences. Ultimately, loops and recursive functions each have their pros and cons depending on the implementation. 

Thinking Recursively

The main reason why people use recursion instead of loops is to avoid destructive state changes. Notice that when we use the loop, we have to change the variable for each iteration of the loop. In our recursive example, the original value of the variable does not change because each function call creates a new one. In more complex programs, it can be beneficial to avoid destructive state changes by using recursion.

One of the more famous cases of recursion is the Fibonacci series algorithm. We can use recursive function calls to represent this infinite series.

fibonacci-recursion

In this function example, we have three different return statements. If we break down how this function works, we can see a bit more how to think recursively. Because of the if statements, if we put one or zero into the function we will get those same numbers back. The recursion takes place with numbers greater than one. If we put two into our function, we call the function again for fib(2-1) + fib(2-2). This is just like calling zero and one and then adding those two together to get one. If we put three into the function, we will call fib(3-1) + fib(3-2). We can simplify this down to fib(1) + fib(0) + fib(1). We can keep doing this with ever higher numbers.

As you can see, our Fibonacci series function is just a combination of ones and zeroes. The return we get is the value at that term of the Fibonacci series. For fib(6) we get a return of eight for example because eight is the sixth term in the series. 

Conclusion

In this post, we took a look at recursion in Go. We talked about what recursion is and how we can think recursively. Our next few posts will continue to look at the different styles of functions in Go.