How to Use Recursion in Go: Simple Guide with Examples

In Go, recursion is when a function calls itself to solve smaller parts of a problem. Use func to define a function that calls itself with a base case to stop the calls and avoid infinite loops.

Syntax

Recursion in Go uses a function that calls itself. It must have a base case to stop calling itself, or it will run forever and crash. The function usually calls itself with a smaller or simpler input.

• func: declares the function
• Function name: the name you choose
• Parameters: inputs to the function
• Return type: output of the function
• Base case: condition to stop recursion
• Recursive call: function calling itself

go

func recursiveFunction(param int) int {
    if param <= 0 { // base case
        return 0
    }
    return param + recursiveFunction(param-1) // recursive call
}

Example

This example shows how to calculate the factorial of a number using recursion. Factorial means multiplying a number by all numbers below it down to 1.

go

package main

import "fmt"

func factorial(n int) int {
    if n <= 1 { // base case
        return 1
    }
    return n * factorial(n-1) // recursive call
}

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

Output

120

Common Pitfalls

Common mistakes when using recursion in Go include:

• Missing or incorrect base case, causing infinite recursion and program crash.
• Not reducing the problem size in recursive calls, so the function never reaches the base case.
• Using recursion for very deep calls without optimization, which can cause stack overflow.

Always ensure your base case is reachable and your recursive call moves toward it.

go

package main

import "fmt"

// Wrong: no base case, causes infinite recursion
func wrongRecursion(n int) int {
    return n + wrongRecursion(n-1)
}

// Right: with base case
func rightRecursion(n int) int {
    if n <= 0 {
        return 0
    }
    return n + rightRecursion(n-1)
}

func main() {
    // fmt.Println(wrongRecursion(5)) // Uncommenting this will crash the program
    fmt.Println(rightRecursion(5)) // Output: 15
}

Output

15

Quick Reference

• Always define a base case to stop recursion.
• Make sure each recursive call simplifies the problem.
• Use recursion for problems naturally defined by smaller subproblems.
• Test with small inputs first to avoid infinite loops.

Key Takeaways

Recursion in Go means a function calls itself with a smaller input until a base case stops it.

Always include a base case to prevent infinite recursion and program crashes.

Each recursive call should move closer to the base case by simplifying the problem.

Test recursive functions with small inputs to ensure correctness and avoid stack overflow.

Use recursion for problems like factorial, Fibonacci, and tree traversals where subproblems repeat.