public class FactorialExample {
    public static int factorial(int n) {
        if (n == 0) {
            return 1; // Базовый случай
        } else {
            return n * factorial(n - 1); // Рекурсивный случай
        }
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}
В этом примере функция factorial вызывает саму себя, пока не достигнет базового случая, когда n равно 0.

public class DirectRecursionExample {
    public static void countdown(int n) {
        if (n == 0) {
            System.out.println("Done!");
        } else {
            System.out.println(n);
            countdown(n - 1); // Прямой рекурсивный вызов
        }
    }

    public static void main(String[] args) {
        countdown(5);
    }
}

public class IndirectRecursionExample {
    public static void functionA(int n) {
        if (n > 0) {
            System.out.println("A: " + n);
            functionB(n - 1);
        }
    }

    public static void functionB(int n) {
        if (n > 0) {
            System.out.println("B: " + n);
            functionA(n - 1);
        }
    }

    public static void main(String[] args) {
        functionA(5);
    }
}

public class TailRecursionExample {
    public static int tailFactorial(int n, int acc) {
        if (n == 0) {
            return acc;
        } else {
            return tailFactorial(n - 1, n * acc); // Хвостовой рекурсивный вызов
        }
    }

    public static void main(String[] args) {
        int result = tailFactorial(5, 1);
        System.out.println("Factorial of 5 is: " + result);
    }
}
В этом примере хвостовая рекурсия позволяет эффективно вычислить факториал без необходимости удерживать промежуточные результаты в стеке вызовов.

public class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
        left = right = null;
    }
}

public class TreeTraversal {
    public static void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left); // Рекурсивный вызов для левого поддерева
            System.out.println(node.value);
            inOrder(node.right); // Рекурсивный вызов для правого поддерева
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        inOrder(root);
    }
}
В этом примере используется нерегулярная рекурсия для обхода бинарного дерева в порядке in-order.

factorial(3)
  -> 3 * factorial(2)
      -> 2 * factorial(1)
          -> 1 * factorial(0)
              -> return 1
          -> return 1 * 1 = 1
      -> return 2 * 1 = 2
  -> return 3 * 2 = 6
На каждом этапе рекурсивного вызова в стек добавляется новый фрейм. Когда функция достигает базового случая (factorial(0)), она начинает возвращаться, удаляя фреймы из стека и комбинируя результаты.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) для n > 1

public class FibonacciExample {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // Базовый случай
        } else if (n == 1) {
            return 1; // Базовый случай
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // Рекурсивный случай
        }
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
    }
}
Этот код вычисляет 10-е число Фибоначчи. Однако, такой подход неэффективен для больших значений n, так как происходит многократное вычисление одних и тех же значений. В таких случаях лучше использовать динамическое программирование или итеративные решения.

public class ReverseStringExample {
    public static String reverse(String str) {
        if (str.isEmpty()) {
            return str; // Базовый случай
        }
        return reverse(str.substring(1)) + str.charAt(0); // Рекурсивный случай
    }

    public static void main(String[] args) {
        String original = "hello";
        String reversed = reverse(original);
        System.out.println("Original: " + original);
        System.out.println("Reversed: " + reversed);
    }
}
Этот код переворачивает строку "hello" и выводит "olleh". Рекурсивная функция reverse удаляет первый символ строки и добавляет его в конец результата рекурсивного вызова.

public class MaxElementExample {
    public static int findMax(int[] arr, int n) {
        if (n == 1) {
            return arr[0]; // Базовый случай: один элемент
        }
        return Math.max(arr[n - 1], findMax(arr, n - 1)); // Рекурсивный случай
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 3, 9, 2};
        int max = findMax(array, array.length);
        System.out.println("Maximum element is: " + max);
    }
}
Этот код ищет максимальный элемент в массиве [1, 5, 3, 9, 2], и выводит 9.

import java.io.File;

public class DirectoryTraversalExample {
    public static void listFiles(File dir) {
        File[] files = dir.listFiles();
        if (files != null) {
            for (File file : files) {
                if (file.isDirectory()) {
                    listFiles(file); // Рекурсивный случай: обход поддиректории
                } else {
                    System.out.println("File: " + file.getAbsolutePath());
                }
            }
        }
    }

    public static void main(String[] args) {
        File dir = new File("/path/to/directory");
        listFiles(dir);
    }
}
Этот код рекурсивно обходит директорию и все её поддиректории, выводя полные пути к файлам.

public class TowerOfHanoiExample {
    public static void solveHanoi(int n, char fromRod, char toRod, char auxRod) {
        if (n == 1) {
            System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
            return;
        }
        solveHanoi(n - 1, fromRod, auxRod, toRod);
        System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
        solveHanoi(n - 1, auxRod, toRod, fromRod);
    }

    public static void main(String[] args) {
        int n = 3; // Количество дисков
        solveHanoi(n, 'A', 'C', 'B');  // A, B и C - названия стержней
    }
}
Этот код решает задачу о Ханойской башне для трех дисков. Рекурсивная функция перемещает диски между стержнями согласно правилам задачи.

public class PermutationsExample {
    public static void permute(String str, int l, int r) {
        if (l == r) {
            System.out.println(str);
        } else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permute(str, l + 1, r);
                str = swap(str, l, i); // Возврат к исходному состоянию
            }
        }
    }

    public static String swap(String str, int i, int j) {
        char[] charArray = str.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    public static void main(String[] args) {
        String str = "ABC";
        int n = str.length();
        permute(str, 0, n - 1);
    }
}
Этот код генерирует все перестановки строки "ABC" и выводит их.