// 第 12 周 – 经典的递归函数
// 运行：go run ./w12/examples
package main

import "fmt"

func sum(a []int) int {
	if len(a) == 0 {
		return 0
	}
	return a[0] + sum(a[1:]) // 切片的“其余部分”，不复制
}

func power(x int64, n int) int64 {
	if n == 0 {
		return 1
	}
	return x * power(x, n-1)
}

func fastPower(x int64, n int) int64 { // O(log n)
	if n == 0 {
		return 1
	}
	half := fastPower(x, n/2)
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

func reverse(r []rune) string {
	if len(r) == 0 {
		return ""
	}
	return reverse(r[1:]) + string(r[0])
}

func isPalindrome(r []rune) bool {
	if len(r) < 2 {
		return true
	}
	return r[0] == r[len(r)-1] && isPalindrome(r[1:len(r)-1])
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func binarySearch(a []int, x, lo, hi int) int {
	if lo > hi {
		return -1
	}
	mid := lo + (hi-lo)/2
	switch {
	case a[mid] == x:
		return mid
	case a[mid] < x:
		return binarySearch(a, x, mid+1, hi)
	default:
		return binarySearch(a, x, lo, mid-1)
	}
}

func digits(n int) int {
	if n < 10 {
		return 1
	}
	return 1 + digits(n/10)
}

func main() {
	fmt.Println("sum =", sum([]int{3, 1, 4, 1, 5, 9, 2, 6}))
	fmt.Println("power(2, 10) =", power(2, 10), ", fastPower(3, 13) =", fastPower(3, 13))
	fmt.Println(`reverse("recursion") =`, reverse([]rune("recursion")))
	fmt.Println(`isPalindrome("上海自来水来自海上") =`, isPalindrome([]rune("上海自来水来自海上")))
	fmt.Println("gcd(1071, 462) =", gcd(1071, 462))
	s := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	fmt.Println("binarySearch(23) =", binarySearch(s, 23, 0, len(s)-1))
	fmt.Println("digits(2026) =", digits(2026))
}