Go Recursion
Functions that call themselves in Go
🔄 What is Recursion?
Recursion occurs when a function calls itself to solve smaller versions of the same problem. It requires a base case to stop and a recursive case to continue the process.
// Recursive function to calculate factorial
func factorial(n int) int {
if n <= 1 {
return 1 // Base case
}
return n * factorial(n-1) // Recursive case
}
func main() {
result := factorial(5)
fmt.Println("5! =", result)
}
Output:
5! = 120
Key Recursion Concepts
Base Case
Condition that stops the recursion
if n <= 1 {
return 1 // Stop here
}Recursive Case
Function calls itself with modified input
return n * factorial(n-1)Problem Reduction
Each call works on a smaller problem
factorial(5) → factorial(4) → ...Call Stack
Functions stack up until base case
// Stack builds up then unwinds🔹 Basic Recursion Examples
Simple recursive functions to understand the concept:
package main
import "fmt"
// Calculate factorial recursively
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}
// Count down recursively
func countdown(n int) {
if n <= 0 {
fmt.Println("Done!")
return
}
fmt.Println(n)
countdown(n - 1)
}
// Calculate sum of numbers from 1 to n
func sumToN(n int) int {
if n <= 1 {
return n
}
return n + sumToN(n-1)
}
func main() {
// Factorial example
fmt.Println("Factorial of 4:", factorial(4))
// Countdown example
fmt.Println("Countdown from 5:")
countdown(5)
// Sum example
fmt.Println("Sum 1 to 10:", sumToN(10))
}Output:
Factorial of 4: 24
Countdown from 5:
5
4
3
2
1
Done!
Sum 1 to 10: 55
🔹 Fibonacci Sequence
Classic recursion example - Fibonacci numbers:
package main
import "fmt"
// Calculate nth Fibonacci number
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2)
}
// Print Fibonacci sequence up to n terms
func printFibonacci(n int) {
fmt.Print("Fibonacci sequence: ")
for i := 0; i < n; i++ {
if i > 0 {
fmt.Print(", ")
}
fmt.Print(fibonacci(i))
}
fmt.Println()
}
func main() {
// Single Fibonacci number
fmt.Println("Fibonacci(7):", fibonacci(7))
// Fibonacci sequence
printFibonacci(10)
}Output:
Fibonacci(7): 13
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
🔹 String and Slice Recursion
Recursive functions working with strings and slices:
package main
import "fmt"
// Reverse a string recursively
func reverseString(s string) string {
if len(s) <= 1 {
return s
}
return reverseString(s[1:]) + string(s[0])
}
// Check if string is palindrome
func isPalindrome(s string) bool {
if len(s) <= 1 {
return true
}
if s[0] != s[len(s)-1] {
return false
}
return isPalindrome(s[1 : len(s)-1])
}
// Sum all elements in slice
func sumSlice(numbers []int) int {
if len(numbers) == 0 {
return 0
}
if len(numbers) == 1 {
return numbers[0]
}
return numbers[0] + sumSlice(numbers[1:])
}
func main() {
// String reversal
original := "hello"
reversed := reverseString(original)
fmt.Printf("'%s' reversed is '%s'\n", original, reversed)
// Palindrome check
word1 := "racecar"
word2 := "hello"
fmt.Printf("'%s' is palindrome: %t\n", word1, isPalindrome(word1))
fmt.Printf("'%s' is palindrome: %t\n", word2, isPalindrome(word2))
// Slice sum
numbers := []int{1, 2, 3, 4, 5}
sum := sumSlice(numbers)
fmt.Printf("Sum of %v is %d\n", numbers, sum)
}Output:
'hello' reversed is 'olleh'
'racecar' is palindrome: true
'hello' is palindrome: false
Sum of [1 2 3 4 5] is 15