// 16_Recursion.java - רקורסיה

public class Recursion {
    public static void main(String[] args) {
        // עצרת
        System.out.println("--- עצרת ---");
        System.out.println("5! = " + factorial(5));
        System.out.println("7! = " + factorial(7));
        System.out.println("10! = " + factorial(10));

        // סכום 1..n
        System.out.println("\n--- סכום ---");
        System.out.println("סכום 1..10 = " + sum(10));
        System.out.println("סכום 1..100 = " + sum(100));

        // פיבונאצ'י
        System.out.println("\n--- פיבונאצ'י ---");
        System.out.print("10 הראשונים: ");
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();

        // חזקה
        System.out.println("\n--- חזקה ---");
        System.out.println("2^10 = " + power(2, 10));
        System.out.println("3^5 = " + power(3, 5));

        // היפוך מחרוזת
        System.out.println("\n--- היפוך מחרוזת ---");
        System.out.println(reverse("hello"));
        System.out.println(reverse("abcdef"));

        // בדיקת פלינדרום
        System.out.println("\n--- פלינדרום ---");
        System.out.println("level: " + isPalindrome("level"));
        System.out.println("hello: " + isPalindrome("hello"));
        System.out.println("racecar: " + isPalindrome("racecar"));

        // ספירת ספרות
        System.out.println("\n--- ספירת ספרות ---");
        System.out.println("ספרות של 12345: " + countDigits(12345));
        System.out.println("ספרות של 7: " + countDigits(7));

        // GCD - מחלק משותף מקסימלי
        System.out.println("\n--- GCD ---");
        System.out.println("gcd(48, 18) = " + gcd(48, 18));
        System.out.println("gcd(100, 75) = " + gcd(100, 75));
    }

    // עצרת
    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    // סכום 1..n
    public static int sum(int n) {
        if (n <= 0) return 0;
        return n + sum(n - 1);
    }

    // פיבונאצ'י
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // חזקה
    public static long power(int base, int exp) {
        if (exp == 0) return 1;
        return base * power(base, exp - 1);
    }

    // היפוך מחרוזת
    public static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    // פלינדרום
    public static boolean isPalindrome(String s) {
        if (s.length() <= 1) return true;
        if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
        return isPalindrome(s.substring(1, s.length() - 1));
    }

    // ספירת ספרות
    public static int countDigits(int n) {
        if (n < 10) return 1;
        return 1 + countDigits(n / 10);
    }

    // GCD - אלגוריתם אוקלידס
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}