Recursive Functions

A recursive function calls itself to solve smaller versions of a problem. Every correct terminating recursion needs a base case.

The base case handles a small input without making another recursive call. The recursive case reduces the problem and uses the result. For factorial, factorial(n) = n * factorial(n-1) for positive n, while factorial(0) is 1.

Each call has its own parameters and local variables. Deep recursion consumes call-stack space, and some algorithms are more naturally expressed with a loop. Never recurse without making progress toward the base case.

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 {
	if n <= 1 {
		return 1
	}
	return n * factorial(n-1)
}
func main() {
	fmt.Println("Factorial 4:", factorial(4))
	fmt.Println("Factorial 0:", factorial(0))
}

Output

Factorial 4: 24
Factorial 0: 1

factorial(4) needs 4 * factorial(3), then 3 * factorial(2), then 2 * factorial(1). The last call returns 1. As calls finish, the results combine to produce 24. This example assumes a nonnegative input; its simple base-case check also returns 1 for negative values rather than validating them.

• An absent or unreachable base case causes continued recursive calls and eventual failure.
• Factorials grow rapidly and overflow fixed-size integer types for sufficiently large inputs.

Write a recursive sumTo(n) that returns 1+2+...+n for nonnegative n. Trace sumTo(3) by hand.

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

You have practiced Recursive Functions 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.