Recursion is one of the important concepts in programming languages. In this post, we will learn how to use recursion in Go.
What is Recursion?
Recursion happens when a function calls itself, i.e it recurs. When a function inside a program calls itself recursion occurs.
Criteria for Recursion
To be a recursive function it has to fulfill some predefined conditions. These are:
- It calls itself.
- It has a stopping condition.
Those functions which don’t follow the rule can be called an infinitely recursive function.
Recursion types
There can be two types of recursion as explained above. First is the finite or regular recursion and the other, which is infinite recursion. Let’s see what those are.
1. Finite recursion
Finite recursion or simply recursion is the state of function in which:
- The function calls itself.
- It stops at the boundary condition.
Below is an example of a finite recursion.
package main
import (
"fmt"
)
func recurFact(v int) int {
if (v == 0) {
return 1
} else {
return v * recurFact(v-1)
}
}
func main() {
n := recurFact(10)
fmt.Println(n) // 3628800
}
2. Infinite recursion
Infinite recursion happens when the second condition is not followed. Or to put it simply, the function doesn’t stop calling itself. Here is an infinite recursion in action.
package main
import (
"fmt"
)
func recurse() {
fmt.Println("Endless!")
recurse()
}
func main() {
// recurse() // infinite call
}
Recursion methods
Recursion has different methods or order of calling itself by which it can be classified into two different types. The first one being regular while the second one is tail-recursive. Let’s have a look at each one of them.
1. Regular recursion
Regular recursion is when calling itself does not finish the calculation immediately instead it passes it down the hierarchy. Below is an example showing that.
package main
import (
"fmt"
)
func fib(n int) int {
if (n == 0) {
return 0
} else if(n == 1) {
return 1
} else {
return fib(n-1) + fib(n-2)
}
}
func main() {
fmt.Println(fib(10)) // 55
}
2. Tail-recursion
Tail recursion happens when a function calling itself calculates the value and sends it down the hierarchy. Here is an example of a tail-recursion.
package main
import (
"fmt"
)
func f(v int) {
if(v == 0) {
fmt.Println("Zero")
return
} else {
fmt.Println(v)
f(v-1) // tail-recursive call
}
}
func main() {
f(5)
// output:
// 5
// 4
// 3
// 2
// 1
// Zero
}
Tail-recursion benefits
The tail-calls are beneficial in an aspect that it is optimized by compilers in many cases. So, it is almost always faster than a normal recursive call.
Function types
Both types of functions can be used for recursion. The regular ones and the anonymous function.
1. Regular function
Here is a regular function showing recursive nature.
package main
import (
"fmt"
)
func f(v int) {
if(v == 0) {
return
} else {
fmt.Println(v)
f(v-1)
}
}
func main() {
f(5)
// output:
// 5
// 4
// 3
// 2
// 1
// Zero
}
2. Anonymous function
Anonymous functions can be recursive as well. Here is an anonymous function showing recursion.
package main
import (
"fmt"
)
func main() {
var f func(int)
f = func(v int) {
if(v == 5) {
fmt.Println("Done")
return
} else {
fmt.Println(v)
f(v-1)
}
}
f(9)
// Output:
// 9
// 8
// 7
// 6
// Done
}