Recursion
func name(n int) int {
if n <= baseCase {
return value
}
return name(n - 1)
}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
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function factorial
func factorial(n int) int {
// Check whether n <= 1
if n <= 1 {
// Send 1 back to the caller
return 1
}
// Send n * factorial(n-1) back to the caller
return n * factorial(n-1)
}
// main is where the program starts running
func main() {
// Print the values followed by a newline
fmt.Println(factorial(5))
}Login to try C/C++/Java/PHP code in the editor
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.
Example: The Importance of a Base Case
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function countdown
func countdown(n int) {
// Check whether n <= 0
if n <= 0 {
// Print the values followed by a newline
fmt.Println("liftoff!")
return
}
// Print the values followed by a newline
fmt.Println(n)
countdown(n - 1)
}
// main is where the program starts running
func main() {
countdown(3)
}Login to try C/C++/Java/PHP code in the editor
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
// Every Go file belongs to a package; main builds an executable
package main
// Import the fmt package
import "fmt"
// Define the function sumSlice
func sumSlice(nums []int) int {
// Check whether len(nums) == 0
if len(nums) == 0 {
// Send 0 back to the caller
return 0
}
// Send nums[0] + sumSlice(nums[1:]) back to the caller
return nums[0] + sumSlice(nums[1:])
}
// main is where the program starts running
func main() {
// Print the values followed by a newline
fmt.Println(sumSlice([]int{1, 2, 3, 4, 5}))
}Login to try C/C++/Java/PHP code in the editor
- Forgetting a base case, causing infinite recursion until the program crashes with a stack overflow.
- Writing recursive Fibonacci or similar without memoization, causing exponential recomputation for larger inputs.
- Assuming Go automatically optimizes tail-recursive calls like some functional languages -- it does not, so deep recursion still consumes stack space.
- A recursive function calls itself with a smaller version of the original problem.
- Every recursive function needs a base case that stops the recursion.
- Go does not perform tail-call optimization, so very deep recursion can exhaust the stack.
- Recursion is a natural fit for problems with a naturally recursive structure, like tree traversal.
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: