The simplest way to structure a Go program is using a set of functions that call one another in a disciplined, hierarchical manner. Functions call one another, but can a function call itself? There are problems that are better described through functions that call themselves. This type of function is called recursion or a recursive function. A recursive function, therefore, is a function that calls itself . However, the function call can be direct or indirect. An indirect recursive function forms a circular definition through other functions, while a direct recursion function is a simple call to itself.
Want to learn Golang programming in an online class or online course setting? We have a list of the Best Online Courses to Learn and Golang to help get you started.
What Are Recursive Acronyms?
With regard to understanding the concepts of recursion, we may slightly detour on the idea of recursive acronyms, as they share a common background. A recursive acronym is an attempt to put a tinge of humor into the definition of abbreviation which otherwise are too technical and dry. However this poetic expression is more reasonably inclined towards explaining a sense of infinity within its definition and not just for comic relief. Anyway, it’s always interesting to read them and certainly more interesting to create one. Although there are many, some popular recursive acronyms we may come across in the field of computing include:
- GNU: GNU Not Unix
- Nano: Nano’s Another Editor
- WINE: WINE Is Not Emulator
- RPM: RPM Package Manager
Note that the idea of recursion (calling itself) is embedded into the abbreviations, which points towards an infinite series of definitions. Analogously, the recursive functions that developers use in our programs are of a similar nature.
What Are Recursive Functions in Go and Golang?
There are certain Go programming problems that are best solved through recursion. These approaches have many common elements; in general, however, a recursive function is called to solve a problem. The recursive function actually knows how to solve the problem using only the base case. Therefore, a function called with base case returns a result. Otherwise, if the case is complex, it divides the problem into two conceptual parts, wherein the first part knows how to solve the problem, and, in another part, it does not know how to do it. So, to make the recursion feasible, the latter part must be converted into a simple definition that can be solved like the first part. Thus, in order to make the new problem look like the original problem, the function launches a fresh call to itself, which is nothing but a copy of itself with a smaller problem. This continuation of the call is called the recursive step.
The recursive step contains a return statement which actually returns the solution, or a portion of the solution, back to its caller, and then to its caller’s caller, and so on in a hierarchical fashion until it reaches the original caller, possibly main.
We expand the problem and lay down the steps until the problem is in the miniature solvable state. Then, we retract back to the origin, in steps. The recursive step executes while the original call to the function is still open and can result in many more such recursive calls as the function keeps subdividing newer sub problems. This means that there must be specific terminating points from where backtracking starts. As the problem converges into smaller subproblems, it eventually reaches to the base case, from where converging stops and returns the result to the previous copy of the function. This retracting sequence ensues all the way up to the original caller.
Reading: Understanding Functions in Go
Go Recursion Code Examples
The following Golang code examples illustrate recursion in Go from a mathematical perspective:
In our first example, programmers can use recursion to define a sequence in Go. For example, the sequence of power of 2 can be obtained using the following:
an=2n, n=0, 1, 2, ….
However, this sequence can also be defined by giving the first term of the sequence, such as:
a0=1
And the rule for finding a term of the sequence from the previous one, namely:
an+1=2an , n=0,1,2,…
Therefore, here we define a sequence recursively by specifying how terms of the sequence are found from previous terms.
Here is another example: Suppose that f is defined recursively by the following:
f(0)=2 f(n+1)=2.f(n)+1;
If we are to find f(4), according to the recursive definition, we can use:
f(1)=2.f(0)+1=2.2+1=5 f(2)=2.f(1)+1=2.5+1=11 f(3)=2.f(2)+ 1=2.11+1=23 f(4)=2.f(3)+1=2.23+1=47
In our third example, we look at a common calculation of finding factorials of a number. The factorial of a nonnegative integer n, written as n! can be written as the product: n . (n-1) . (n-2) . … . 1. So, 1!=1 and 0!=1.
Therefore f(n) = n! can be defined as the recursive function by specifying the initial value of the function f(0)=1 and giving a rule for finding f(n+1) from f(n). This is obtained by noting that (n+1)! is computed from n! by multiplying by n+1. Therefore, the rule is:
f(n+1)=(n+1).f(n)
To determine:
f(5)=5! F(5)=5.f(4)=5.4.f(3)=5.4.3.f(2)=5.4.3.2.f(1)=5.4.3.2.1.f(0)=5.4. 3.2.1.1=120
Recursive Program Example in Go and Golang
The factorial, as exemplified in our previous Go code example, can be implemented through code iteratively (non-recursively) by using for statements (or for loops) as shown here:
func fact(num int) int { f := 1 for i := num; i >= 1; i– { f *= i } return f }
But, according to the nature of the function, it is best coded recursively, as follows:
func fact2(num int) int { if num <= 1 { return 1 } else { return num * fact2(num-1) } }
The evaluation of the factorial (5!) function is as follows:
Note that the succession of recursive function calls proceeds until 1! is evaluated to be 1. This terminates the recursive and the values start to be returned from each recursive call to its caller until the final value is calculated and returned.
Fibonacci Function in Go Using Recursion
There are many problems in computing that are better described recursively. A famous among them is finding the Fibonacci series. Here is some example code showing some quick variation of Fibonacci functions in Golang using recursion:
package main import “fmt” func fibonacci1(num int) int { if num == 0 { return 0 } else if num == 1 { return 1 } else { return fibonacci1(num-1) + fibonacci1(num-2) } } func fibonacci2(num int) int { if num == 0 || num == 1 { return num } else { return fibonacci2(num-1) + fibonacci2(num-2) } } func fact(num int) int { f := 1 for i := num; i >= 1; i– { f *= i } return f } func fact2(num int) int { if num <= 1 { return 1 } else { return num * fact2(num-1) } } func main() { for i : = 0; i < 10; i++ { fmt.Print(fibonacci1(i), ", ") } fmt.Println() for i := 0; i < 10; i++ { fmt.Print(fibonacci2(i), ", ") } fmt.Println(fact2(5)) }
Recursion vs. Iteration in Go and Golang
Any problem that is solved recursively can also be solved iteratively. Both iteration and recursion use a control statement, where the former uses repetition structure and the later uses selection structure, respectively. Iteration explicitly uses repetition, whereas repetition is achieved in recursion through repeated function calls. Both use termination tests to end the repetition cycle.
Recursion should be used for those problems that are better described recursively. In fact, iterative solutions have a better performance if we take into account the negatives of recursion. A recursion has an overhead of function calls, which is pretty expensive in terms of processor time and memory space. Recursive function calls cause another copy of the function to be created. In the iterative solution, on the other hand, everything occurs within the function, so the overhead of recursion does not arise.
You can learn more about iteration, control structures, and loops in our tutorial: Understanding Control Structures in Go.
Final Thought on Go and Golang Recursion and Recursive Functions
Recursion is found in almost all programming languages, by it Go or any other. The implementation is also quite similar. There are different types of recursion, such as direct and indirect, but the point is, it is a successive call to the function itself and stops only at the base condition given from where the return begins. Any problem that can be solved using recursion can also be solved non-recursively. There are problems whose solutions are naturally inclined towards a recursive approach. Although an iterative approach to the solution is possible, recursion is preferred, perhaps because the solution is easier to understand and debug.
read more Go and Golang programming tutorials and software development tips.
