Recursion

A Basic Recursive Function

A recursive function calls itself, typically with a smaller or simpler input each time, until it reaches a base case that can be answered directly without further recursion. Factorial is the classic first example.

Example: A Basic Recursive Function

package main

import "fmt"

func factorial(n int) int {
	if n <= 1 {
		return 1
	}
	return n * factorial(n-1)
}

func main() {
	fmt.Println(factorial(5))
}

The Importance of a Base Case

Without a base case that stops the recursion, a recursive function calls itself forever (until the program crashes from stack exhaustion). The base case is what turns an infinite chain of calls into a function that actually terminates.

Note: Always verify the recursive argument moves toward the base case on every call.

Example: The Importance of a Base Case

package main

import "fmt"

func countdown(n int) {
	if n <= 0 {
		fmt.Println("liftoff!")
		return
	}
	fmt.Println(n)
	countdown(n - 1)
}

func main() {
	countdown(3)
}

Recursion on Recursive Data

Recursion is especially natural for data that is itself recursively structured, like computing the sum of a slice by adding its first element to the sum of the rest -- each recursive call handles one smaller piece of the same shape of problem.

Example: Recursion on Recursive Data

package main

import "fmt"

func sumSlice(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	return nums[0] + sumSlice(nums[1:])
}

func main() {
	fmt.Println(sumSlice([]int{1, 2, 3, 4, 5}))
}