#!/usr/bin/env catnip
# Exemples de récursion terminale
# ======================
# Montre l'optimisation automatique des appels terminaux en Catnip

# Récursion terminale de base : factorielle
# --------------------------------
# Tous les appels récursifs sont en position terminale (dernière opération)
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

# Peut gérer une récursion profonde sans débordement de pile
print("factorial(100) digits:", len(str(factorial(100))))  # 158 digits

# Exemple de compte à rebours
# -----------------
countdown = (n) => {
    if n == 0 {
        print("Liftoff!")
        "Done"
    } else {
        print(n)
        countdown(n - 1)  # Appel terminal
    }
}

countdown(5)

# Somme de 1 à N (récursion terminale)
# ---------------------------------
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

# Somme d'intervalle (récursion terminale)
# ---------------------------
range_sum = (start, end, acc=0) => {
    if start > end { acc }
    else { range_sum(start + 1, end, acc + start) }  # Appel terminal
}

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

# PGCD (plus grand commun diviseur) - algorithme d'Euclide
# ----------------------------------------------------
gcd = (a, b) => {
    if b == 0 { a }
    else { gcd(b, a % b) }  # Appel terminal
}

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

# Fonction puissance (récursion terminale)
# --------------------------------
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

# Comparaison : non terminale vs terminale
# ---------------------------------------
# Non terminale : l'appel récursif n'est PAS en position finale

fib_non_tail = (n) => {
    if n <= 1 { n }
    else {
        fib_non_tail(n - 1) + fib_non_tail(n - 2)  # tree recursion, not a TCO candidate
    }
}

# Version terminale avec accumulateur
fib_tail = (n, a=0, b=1) => {
    if n == 0 { a }
    else { fib_tail(n - 1, b, a + b) }  # Appel terminal
}

print("\n--- Comparaison Fibonacci ---")
print("Fib non terminale(10) :", fib_non_tail(10))  # Lente, temps exponentiel
print("Fib terminale(10) :", fib_tail(10))          # Rapide, temps linéaire
print("Fib terminale(100) :", fib_tail(100))        # Fonctionne pour de grandes valeurs de N

# Comment ça marche
# ------------
# Catnip transforme automatiquement les fonctions terminales récursives en boucles `while` :
#
# factorial = (n, acc=1) => {
#     if n <= 1 { acc }
#     else { factorial(n - 1, n * acc) }
# }
#
# Devient (conceptuellement) :
#
# 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
#     }
# }
#
# Avantages :
# - Espace pile en O(1) (pas de débordement de pile)
# - Performances proches d'une boucle native
# - Aucune conversion manuelle nécessaire