How to write a Recursive Function in Go

Click to subscribe to my newsletter
Click to follow me on twitter
Click to view my Github

I don't know about you, but when I started programming the term Recursion made me quiver a bit. I think this is a natural response honestly. New things can be scary! I also did not understand the importance or the potential impact that using Recursion in your code could have. If you don't have a solid grasp on Recursion, you are in luck! I am going to discuss how you can harness the power of Recursion and use it in your Go programs.

So, What is Recursion?

the repeated application of a procedure or definition

A common use of Recursion in programming is calling a function, inside of the same function. Let me show you an example:

package main
import (
    "fmt"
)

func main() {
    n := factorial(4)
    fmt.Println(n)
}

func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}
// 4 * 3 * 2 * 1

main:

func main() {
    n := factorial(4)
    fmt.Println(n)
}

• Inside of func main we declare the variable n and assign n to the return value of the factorial function
• The factorial function has a single argument, 4 of type int
• On the next line of execution, using the fmt package, we print out the value of n

Quick note: in every Recursive function, there needs to be a "base case".
The base case is most commonly an if statement that when evaluated to "true"
will stop calling the function within the function (stop recursion)
and will allow the program to return out of the function

factorial:

func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}

• Below the main function, we declare a function with an identifier of factorial
• The function factorial has a single parameter, n of type int
• The function factorial returns a value of type int
• In this example, our base case in factorial is an if statement that checks if the value of n is 0
• Because our argument n is 4, this evaluates to false and we continue to the next line of execution
• Our next line is a return statement that has the expression n * factorial(n-1) what does this mean?

n * factorial(n-1):

func factorial(n int) int {
  // n = 4
    if n == 0 {
        return 1
  }
    return n * factorial(n-1)
}

• in the first iteration, the value of n is 4 so we can write this expression like this: 4 * factorial(4-1)
• we can do the subtraction for the argument for factorial, when we do the expression looks like this: 4 * factorial(3)
• now, we know that we have the value of 4; however, we invoke factorial again with the argument 3
• because we invoke factorial, we jump to the first line of execution in the function

func factorial(n int) int {
  // n = 3
    if n == 0 {
        return 1
  }
    return n * factorial(n-1)
}

• we know that the value of n is now 3; therefore, our base case still evaluates to false
• now that the value of n is 3, our return statement now looks like this: 4 * 3 * factorial(3-1)
• simplified: 4 * 3 * factorial(2)
• we invoke factorial again with the argument being the value 2 of type int

func factorial(n int) int {
  // n = 2
    if n == 0 {
        return 1
  }
    return n * factorial(n-1)
}

• our base case still evaluates to false because 2 is not equal to 0
• our return statement now looks something like this: 4 * 3 * 2 * factorial(2-1)
• simplified: 4 * 3 * 2 * factorial(1)
• we invoke factorial again with the argument being the value 1 of type int

func factorial(n int) int {
  // n = 1
    if n == 0 {
        return 1
  }
    return n * factorial(n-1)
}

• our base case still evaluates to false because 1 is not equal to 0
• our return statement now looks something like this: 4 * 3 * 2 * 1 * factorial(1-1)
• simplified: 4 * 3 * 2 * 1 * factorial(0)

func factorial(n int) int {
  // n = 0
    if n == 0 {
    // true, return 1
        return 1
  }
  return n * factorial(n-1)
}

• this time, our base case still evaluates to true because 0 is equal to 0
• inside of our base case we return the value 1 of type int
• now that our Recursion is done, our final return statement will look like this: return 4 * 3 * 2 * 1 which evaluates to the value 24 of type int

main:

func main() {
  n := factorial(4)
  fmt.Println(n)
  // 24
}

• now that all execution is complete, the value of n is evaluated to 24, this value is printed out on the next line

In Summary

I hope you have enjoyed learning about Recursion. Although, this example is not overly complex, I hope that you can walk away after reading this post with a better understanding of the principles of Recursion and apply them in your workflow. I will say, there should be a level of caution when writing recursive functions. If your base case is not sound, you could find yourself in a position where your function can continually call itself and inevitably cause a stack overflow. However, when done right, Recursion allows us to write clean, DRY, and efficient code.

Next week I will be discussing Pointers, JSON Marshalling, and JSON Unmarshalling. See you then!