# Tail Recursion Examples
# ======================
# Demonstrates automatic tail-call optimization in Catnip

# Basic tail recursion: factorial
# --------------------------------
# All recursive calls are in tail position (last operation)
factorial = (n, acc=1) => {
    if n <= 1 { acc }
    else { factorial(n - 1, n * acc) }
}

print("factorial(5) =", factorial(5))    # 120
print("factorial(10) =", factorial(10))  # 3628800

# Can handle deep recursion without stack overflow
print("factorial(100) digits:", len(str(factorial(100))))  # 158 digits


# Countdown example
# -----------------
countdown = (n) => {
    if n == 0 {
        print("Liftoff!")
        "Done"
    } else {
        print(n)
        countdown(n - 1)  # Tail call
    }
}

countdown(5)


# Sum from 1 to N (tail recursive)
# ---------------------------------
sum_to = (n, acc=0) => {
    if n == 0 { acc }
    else { sum_to(n - 1, acc + n) }
}

print("\nsum_to(100) =", sum_to(100))    # 5050
print("sum_to(1000) =", sum_to(1000))    # 500500


# Range sum (tail recursive)
# ---------------------------
range_sum = (start, end, acc=0) => {
    if start > end { acc }
    else { range_sum(start + 1, end, acc + start) }  # Tail call
}

print("\nrange_sum(1, 10) =", range_sum(1, 10, 0))  # 55
print("range_sum(50, 100) =", range_sum(50, 100, 0))  # 3825


# GCD (greatest common divisor) - Euclidean algorithm
# ----------------------------------------------------
gcd = (a, b) => {
    if b == 0 { a }
    else { gcd(b, a % b) }  # Tail call
}

print("\ngcd(48, 18) =", gcd(48, 18))    # 6
print("gcd(1071, 462) =", gcd(1071, 462))  # 21


# Power function (tail recursive)
# --------------------------------
power = (base, exp, acc=1) => {
    if exp == 0 { acc }
    else { power(base, exp - 1, acc * base) }
}

print("\npower(2, 10) =", power(2, 10))  # 1024
print("power(3, 5) =", power(3, 5))      # 243


# Comparison: Non-tail vs Tail recursive
# ---------------------------------------
# Non-tail: recursive call NOT in final position

fib_non_tail = (n) => {
    if n <= 1 { n }
    else {
        fib_non_tail(n - 1) + fib_non_tail(n - 2)  # Addition after calls
    }
}

# Tail-recursive version with accumulator
fib_tail = (n, a=0, b=1) => {
    if n == 0 { a }
    else { fib_tail(n - 1, b, a + b) }  # Tail call
}

print("\n--- Fibonacci Comparison ---")
print("Non-tail fib(10):", fib_non_tail(10))  # Slow, exponential time
print("Tail fib(10):", fib_tail(10))          # Fast, linear time
print("Tail fib(100):", fib_tail(100))        # Works for large N!


# How it works
# ------------
# Catnip automatically transforms tail-recursive functions into while loops:
#
# factorial = (n, acc=1) => {
#     if n <= 1 { acc }
#     else { factorial(n - 1, n * acc) }
# }
#
# Becomes (conceptually):
#
# factorial = (n, acc=1) => {
#     while true {
#         if n <= 1 { return acc }
#         tmp_0 = n - 1
#         tmp_1 = n * acc
#         n = tmp_0
#         acc = tmp_1
#     }
# }
#
# Benefits:
# - O(1) stack space (no stack overflow)
# - Near-native loop performance
# - No manual conversion needed