Recursion

package main

import "fmt"

// 1. Faktorial dengan rekursi
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)
}

// 2. Fibonacci dengan rekursi
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

// 3. Fibonacci dengan memoization
func fibonacciMemo(n int, memo map[int]int) int {
    if val, exists := memo[n]; exists {
        return val
    }
    
    if n <= 1 {
        return n
    }
    
    memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo)
    return memo[n]
}

// 4. Menghitung pangkat dengan rekursi
func power(base, exp int) int {
    if exp == 0 {
        return 1
    }
    return base * power(base, exp-1)
}

// 5. Mencari GCD (Greatest Common Divisor)
func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func main() {
    // Contoh 1: Faktorial
    fmt.Println("Faktorial:")
    for i := 0; i <= 5; i++ {
        fmt.Printf("%d! = %d\n", i, factorial(i))
    }

    // Contoh 2: Fibonacci
    fmt.Println("\nFibonacci (rekursi biasa):")
    for i := 0; i < 10; i++ {
        fmt.Printf("Fib(%d) = %d\n", i, fibonacci(i))
    }

    // Contoh 3: Fibonacci dengan memoization
    fmt.Println("\nFibonacci (dengan memoization):")
    memo := make(map[int]int)
    for i := 0; i < 10; i++ {
        fmt.Printf("Fib(%d) = %d\n", i, fibonacciMemo(i, memo))
    }

    // Contoh 4: Pangkat
    fmt.Println("\nPangkat:")
    fmt.Printf("2^3 = %d\n", power(2, 3))
    fmt.Printf("3^4 = %d\n", power(3, 4))

    // Contoh 5: GCD
    fmt.Println("\nGCD (Greatest Common Divisor):")
    fmt.Printf("GCD(48, 18) = %d\n", gcd(48, 18))
    fmt.Printf("GCD(54, 24) = %d\n", gcd(54, 24))
}