Recursion

A recursive func calls itself. We can perform an exhaustive search (one that generates all possibilities) with recursion.

Suppose we wish to find all possible 3-letter strings with a Go program. We can use recursion for this. We can recursively add letters.

Example program

To begin, we introduce an AddLetter method. This loops over all possible letters to add to a string. It converts them to strings, and appends them to a new string.

Then We call AddLetter() recursively to add more letters after we add a letter.

Finally When the length of the string passed into AddLetter() reaches 3, we have a completed string. We print it to the console.

package main

import (
    "fmt"
    "strings"
)

func AddLetter(value string) {
    // If we have reached 3 letters, print the completed string.
    if len(value) == 3 {
        fmt.Println("Completed string:", strings.ToUpper(value))
        return
    }
    // Loop over all lowercase ASCII chars.
    for i := 0; i < 26; i++ {
        // Get string from int.
        letter := string(97 + i)
        // Create new string with additional letter.
        valueTemp := value + letter
        // Add another letter using recursion.
        AddLetter(valueTemp)
    }
}

func main() {
    // Start with empty string.
    AddLetter("")
}...
Completed string: ZZS
Completed string: ZZT
Completed string: ZZU
Completed string: ZZV
Completed string: ZZW
Completed string: ZZX
Completed string: ZZY
Completed string: ZZZ

Notes, recursion

With recursion, we can perform an exhaustive search. It is also possible to reduce the search by returning early, to avoid unneeded work.

In Go, we have support for recursion. We can call a method within its own body. This can be used to develop powerful brute-search algorithms.