Tail Recursion with @tailrec

import scala.annotation.tailrec

// Standard recursion (stack overflow risk)
def factorialUnsafe(n: BigInt): BigInt =
  if n <= 1 then BigInt(1)
  else n * factorialUnsafe(n - 1)

// Tail-recursive with accumulator
@tailrec
def factorial(n: BigInt, acc: BigInt = 1): BigInt =
  if n <= 1 then acc
  else factorial(n - 1, n * acc)

@tailrec
def gcd(a: Int, b: Int): Int =
  if b == 0 then a
  else gcd(b, a % b)

@tailrec
def fibonacci(n: Int, a: BigInt = 0, b: BigInt = 1): BigInt =
  if n <= 0 then a
  else fibonacci(n - 1, b, a + b)

// Tail-recursive list operations
@tailrec
def sum(list: List[Int], acc: Int = 0): Int = list match
  case Nil => acc
  case head :: tail => sum(tail, acc + head)

@tailrec
def reverseList[A](list: List[A], acc: List[A] = Nil): List[A] = list match
  case Nil => acc
  case head :: tail => reverseList(tail, head :: acc)

@tailrec
def contains[A](list: List[A], target: A): Boolean = list match
  case Nil => false
  case head :: _ if head == target => true
  case _ :: tail => contains(tail, target)

// Tail-recursive power
@tailrec
def power(base: Double, exp: Int, acc: Double = 1.0): Double =
  if exp <= 0 then acc
  else power(base, exp - 1, acc * base)

// Tail-recursive string operations
@tailrec
def countChar(s: String, c: Char, idx: Int = 0, count: Int = 0): Int =
  if idx >= s.length then count
  else if s(idx) == c then countChar(s, c, idx + 1, count + 1)
  else countChar(s, c, idx + 1, count)

@tailrec
def isPalindrome(s: String, left: Int = 0, right: Int = -1): Boolean =
  val r = if right == -1 then s.length - 1 else right
  if left >= r then true
  else if s(left) != s(r) then false
  else isPalindrome(s, left + 1, r - 1)

@main def run(): Unit =
  println(s"10! = ${factorial(10)}")
  println(s"100! = ${factorial(100)}")
  println(s"GCD(48, 18) = ${gcd(48, 18)}")
  println(s"Fib(50) = ${fibonacci(50)}")
  println(s"Sum: ${sum(List(1, 2, 3, 4, 5))}")
  println(s"Reverse: ${reverseList(List(1, 2, 3, 4, 5))}")
  println(s"Contains 3: ${contains(List(1, 2, 3, 4), 3)}")
  println(s"2^10 = ${power(2, 10)}")
  println(s"Count 'l' in 'hello world': ${countChar("hello world", 'l')}")
  println(s"Is 'racecar' palindrome: ${isPalindrome("racecar")}")
  println(s"Is 'hello' palindrome: ${isPalindrome("hello")}")