Recursion Programs

Learn recursion programs through an executable example, then connect the small demonstration to production code.

A recursive function calls itself on a smaller subproblem. Every recursive path needs a base case or another guaranteed stopping condition.

The example computes a factorial for small nonnegative integers. Real applications must consider integer overflow and deep recursion.

Follow this diagram before executing the example. Check where a value or decision changes what runs next.

This example is a complete program. Save it as main.go or paste it into the Go Playground.

Go code

package main

import "fmt"

func factorial(n int) (int, error) {
	if n < 0 {
		return 0, fmt.Errorf("negative input")
	}
	if n <= 1 {
		return 1, nil
	}
	previous, err := factorial(n - 1)
	if err != nil {
		return 0, err
	}
	return n * previous, nil
}
func main() { result, err := factorial(5); fmt.Println("Factorial:", result, "Error:", err) }

Output

Factorial: 120 Error: <nil>

factorial(5) calls factorial(4), continuing until factorial(1) returns 1; multiplication on the way back produces 120.

• For large n, factorial overflows ordinary int even though the recursive logic is correct.
• A base case must be reachable for every valid input.

Print factorial values 0 through 6 and compare recursive and iterative approaches.

Tip: Edit the example above, predict the output, and run the modified code to test your reasoning.

You have practiced Recursion Programs in a small, self-contained program. The important habit is to predict what runs, inspect the actual output and distinguish the language rule from the particular example.

Before continuing, make sure you can explain the program to someone who has not seen it, including the line that changes its result.