Recursive Functions in Go

Recursion is a programming technique in which a function calls itself directly or indirectly.

A recursive function usually consists of two parts:

  1. Base Case: This is the termination condition of recursion, preventing the function from calling itself indefinitely.
  2. Recursive Case: This is the part where the function calls itself, used to break the problem down into smaller subproblems.

In Go, recursion is used similarly to other languages, but some features of Go require attention.

The syntax format is as follows:

func recursion() {
   recursion() /* the function calls itself */
}

func main() {
   recursion()
}

Go supports recursion, but when using recursion, developers need to set an exit condition; otherwise, the recursion will fall into an infinite loop.

Recursive functions are very useful for solving mathematical problems, such as calculating factorials and generating Fibonacci sequences.

factorial

A factorial is the product of a positive integer, denoted asn!. For example:

5! = 5 * 4 * 3 * 2 * 1 = 120

The following example implements factorial using recursive functions in Go:

Example

package main

import "fmt"

// recursive function calculates factorial
func factorial(n int) int {
    // base condition
    if n == 0 {
        return 1
    }
    // recursive condition
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5)) // output: 120
}

Code Explanation

  1. Base condition: whennWhen it equals 0, the function returns 1, because0!Defined as 1.
  2. Recursive condition: the function returnsnmultiplied byfactorial(n-1)As a result, the problem is gradually broken down into smaller subproblems.

The output of executing the above example is:

120

Fibonacci sequence

The following example implements the Fibonacci sequence using recursive functions in Go:

Example

package main

import "fmt"

func fibonacci(n int) int {
  if n < 2 {
   return n
  }
  return fibonacci(n-2) + fibonacci(n-1)
}

func main() {
    var i int
    for i = 0; i < 10; i++ {
       fmt.Printf("%d\t", fibonacci(i))
    }
}

The output of executing the above example is:

0    1    1    2    3    5    8    13    21    34

square root

The following example uses recursion in Go to implement code for finding the square root:

Example

package main

import (
        "fmt"
)

func sqrtRecursive(x, guess, prevGuess, epsilon float64) float64 {
        if diff := guess*guess - x; diff < epsilon && -diff < epsilon {
                return guess
        }

        newGuess := (guess + x/guess) / 2
        if newGuess == prevGuess {
                return guess
        }

        return sqrtRecursive(x, newGuess, guess, epsilon)
}

func sqrt(x float64) float64 {
        return sqrtRecursive(x, 1.0, 0.0, 1e-9)
}

func main() {
        x := 25.0
        result := sqrt(x)
        fmt.Printf("The square root of %.2f is %.6f\n", x, result)
}

In the above example,sqrtRecursiveThe function implements square root calculation using recursion.

sqrtRecursiveThe function accepts four parameters:

  • xRepresents the number whose square root is to be found
  • guessRepresents the current guessed square root value
  • prevGuessRepresents the previous guess value
  • epsilonRepresents the precision requirement (i.e., how close to the square root)

The termination condition for the recursion is that the current guess of the square root is very close to the previous guess, with the difference less than the given precision epsilon.

In the sqrt function, we call sqrtRecursive to calculate the square root, passing in the initial value and precision requirement. Then, in the main function, we call the sqrt function to solve for the square root and print the result.

The output of executing the above code is:

25.00 的平方根为 5.000000

Advantages and disadvantages of recursion

Advantages

  • Conciseness: Recursive code is usually more concise and easier to understand than iterative code.
  • Problem decomposition: Recursion is naturally suitable for solving problems that can be decomposed into similar subproblems, such as tree traversal, divide-and-conquer algorithms, etc.

Disadvantages

  • Performance overhead: Recursive calls consume stack space and may cause stack overflow, especially in deep recursion.
  • Debugging difficulty: Recursive code can be harder to debug, especially when the recursion depth is large.

Recursion and iteration

Recursion and iteration are two different methods for solving problems. Recursion solves a problem by a function calling itself, while iteration uses loop structures (such asforloop) to repeatedly execute a block of code.

Recursion vs Iteration

Features Recursion Iteration
Code conciseness Usually more concise May be more verbose
Performance May be slower and consumes stack space Usually faster and uses less memory
Applicable scenarios Suitable for problems that can be decomposed into subproblems Suitable for linear or simply repeated problems

Common applications of recursion

Recursion is widely used in many algorithms and data structures, for example:

  • Tree and graph traversal: such as depth-first search (DFS).
  • Divide and Conquer Algorithm: such as merge sort, quicksort.
  • Dynamic programming: such as calculating the Fibonacci sequence.

File directory traversal

Example

import (
    "fmt"
    "os"
    "path/filepath"
)

func walkDir(dir string, indent string) {
    entries, err := os.ReadDir(dir)
    if err != nil {
        return
    }

    for _, entry := range entries {
        fmt.Println(indent + entry.Name())
        if entry.IsDir() {
            walkDir(filepath.Join(dir, entry.Name()), indent+"  ")
        }
    }
}

func main() {
    walkDir(".", "")
}

When using recursion in Go, special attention should be paid to the correctness of the base condition (termination condition) to avoid infinite recursion. For performance-sensitive or potentially deeply recursive scenarios, it is recommended to consider iterative implementations or use Go-specific mechanisms such as channels/goroutines.

other extensions