"jjj"
Go Recursion
What is Recursion?
Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. It continues until a base condition is met, preventing infinite loops. Recursion is useful for problems like factorial computation, Fibonacci sequence generation, and tree traversal.
Syntax of Recursion in Go
A recursive function in Go consists of:
- A terminating condition that prevents additional recursive calls.
- A recursive scenario in which the function invokes itself with adjusted parameters.
package main
import "fmt"
// Recursive function example
func recursiveFunction(n int) {
if n <= 0 { // Base case
fmt.Println("Recursion ends here")
return
}
fmt.Println("Current value:", n)
recursiveFunction(n - 1) // Recursive call with decremented value
}
func main() {
recursiveFunction(5)
}OutPut:
Current value: 5 Current value: 4 Current value: 3 Current value: 2 Current value: 1 Recursion ends here
Example 1: Factorial using Recursion
Factorial of a number nnn is defined as:
n!=n×(n−1)×(n−2)×...×1
package main
import "fmt"
// Function to compute factorial recursively
func factorial(n int) int {
if n == 0 {
return 1 // Base case: 0! is 1
}
return n * factorial(n-1) // Recursive case
}
func main() {
num := 5
fmt.Printf("Factorial of %d is %d\n", num, factorial(num))
}OutPut:
Factorial of 5 is 120
Example 2: Fibonacci Sequence with Recursion
The Fibonacci sequence follows the rule:
F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)
where F(0)=0F(0) = 0F(0)=0 and F(1)=1F(1) = 1F(1)=1.
package main
import "fmt"
// Recursive function to calculate Fibonacci numbers
func fibonacci(n int) int {
if n <= 1 {
return n // Base cases: F(0) = 0, F(1) = 1
}
return fibonacci(n-1) + fibonacci(n-2) // Recursive case
}
func main() {
num := 6
fmt.Printf("Fibonacci number at position %d is %d\n", num, fibonacci(num))
}OutPut:
Fibonacci number at position 6 is 8
Example 3: Sum of Digits using Recursion
A function that recursively calculates the sum of digits of a number.
package main
import "fmt"
// Function to compute sum of digits
func sumOfDigits(n int) int {
if n == 0 {
return 0 // Base case: if no digits left
}
return (n % 10) + sumOfDigits(n/10) // Recursive case
}
func main() {
num := 1234
fmt.Printf("Sum of digits of %d is %d\n", num, sumOfDigits(num))
}OutPut:
Sum of digits of 1234 is 10
Example 4: Reverse a String Recursively
A function that reverses a string using recursion.
package main
import "fmt"
// Recursive function to reverse a string
func reverseString(s string) string {
if len(s) == 0 {
return "" // Base case: empty string
}
return string(s[len(s)-1]) + reverseString(s[:len(s)-1]) // Recursive case
}
func main() {
str := "hello"
fmt.Printf("Reversed string: %s\n", reverseString(str))
}OutPut:
Reversed string: olleh
Key Points to Remember About Recursion in Go
- 1. Every recursion must have a base condition to prevent infinite loops.
- 2. Recursive calls consume stack memory, so excessive recursion may cause a stack overflow.
- 3. Tail recursion is not optimized by Go's compiler, so deep recursion should be avoided in performance-critical applications.
- 4. Recursion can be replaced with iteration in some cases for better efficiency.
Prefer Learning by Watching?
Watch these YouTube tutorials to understand GO Tutorial visually:
What You'll Learn:
- 📌 #40 Python Tutorial for Beginners | Recursion
- 📌 18 | Recursion in Go Lang | Go Tutorial | Go Lang Programming