Как называется когда метод вызывает сам себя

Как называется когда метод вызывает сам себя — Рекурсия

Это явление называется рекурсией (recursion). Рекурсия — одна из самых важных техник в программировании, позволяющая решать задачи путём разделения их на меньшие подзадачи.

1. Определение и основные компоненты

Рекурсия — это процесс, при котором функция или метод вызывает сам себя. Каждая рекурсивная функция должна содержать:

1. Базовый случай (Base Case) — условие, при котором рекурсия останавливается
2. Рекурсивный случай — вызов метода с уменьшенным аргументом

public class RecursionBasics {
    // Пример: вычисление факториала
    public static int factorial(int n) {
        // Базовый случай
        if (n <= 1) {
            return 1;
        }
        
        // Рекурсивный случай
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));  // 120
        // factorial(5) → 5 * factorial(4)
        //             → 5 * 4 * factorial(3)
        //             → 5 * 4 * 3 * factorial(2)
        //             → 5 * 4 * 3 * 2 * factorial(1)
        //             → 5 * 4 * 3 * 2 * 1 = 120
    }
}

2. Классические примеры рекурсии

Пример 1: Сумма чисел от 1 до n

public static int sum(int n) {
    // Базовый случай
    if (n <= 0) {
        return 0;
    }
    // Рекурсивный случай: n + сумма предыдущих
    return n + sum(n - 1);
}

System.out.println(sum(5));  // 15 (1+2+3+4+5)

Пример 2: Степень числа

public static int power(int base, int exp) {
    // Базовый случай
    if (exp == 0) {
        return 1;
    }
    // Рекурсивный случай
    return base * power(base, exp - 1);
}

System.out.println(power(2, 5));  // 32

Пример 3: Поиск в массиве

public static int binarySearch(int[] arr, int target, int left, int right) {
    // Базовый случай: элемент не найден
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;  // Найден
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);  // Поиск слева
    } else {
        return binarySearch(arr, target, mid + 1, right);  // Поиск справа
    }
}

3. Обход деревьев (древовидная рекурсия)

Рекурсия особенно полезна при работе с деревьями:

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

public class TreeTraversal {
    // Обход в глубину (DFS)
    public static void preOrder(TreeNode node) {
        if (node == null) {
            return;  // Базовый случай
        }
        
        System.out.println(node.value);  // Обработка текущего узла
        preOrder(node.left);               // Рекурсия влево
        preOrder(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);
        
        preOrder(root);  // 1, 2, 4, 5, 3
    }
}

4. Проблема переполнения стека (Stack Overflow)

Без базового случая или при глубокой рекурсии:

public class StackOverflowExample {
    // ОПАСНО! Бесконечная рекурсия
    public static int badFactorial(int n) {
        return n * badFactorial(n - 1);  // Нет базового случая!
    }
    
    // Это вызовет StackOverflowError после ~10,000 вызовов
    // badFactorial(5);  // StackOverflowError
}

Каждый вызов добавляет фрейм в stack, и если рекурсия слишком глубокая, stack переполняется.

5. Глубина рекурсии

public class RecursionDepth {
    // Отслеживание глубины
    public static int fibonacci(int n, int depth) {
        System.out.println("Глубина: " + depth + ", n=" + n);
        
        if (n <= 1) {
            return n;  // Базовый случай
        }
        
        return fibonacci(n - 1, depth + 1) + fibonacci(n - 2, depth + 1);
    }
    
    public static void main(String[] args) {
        fibonacci(4, 0);
        // Выведет много строк, показывая глубину рекурсии
    }
}

6. Оптимизация: мемоизация

Рекурсия может быть медленной, если пересчитывает одно и то же:

import java.util.HashMap;
import java.util.Map;

public class Memoization {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    // Наивная рекурсия (медленно)
    public static long slowFibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return slowFibonacci(n - 1) + slowFibonacci(n - 2);
    }
    
    // С мемоизацией (быстро)
    public static long fastFibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        
        if (memo.containsKey(n)) {
            return memo.get(n);  // Возвращаем закэшированный результат
        }
        
        long result = fastFibonacci(n - 1) + fastFibonacci(n - 2);
        memo.put(n, result);  // Сохраняем в кэш
        return result;
    }
    
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(slowFibonacci(30));  // ~1 сек
        System.out.println(System.currentTimeMillis() - start);
        
        memo.clear();
        start = System.currentTimeMillis();
        System.out.println(fastFibonacci(30));  // ~1 мс
        System.out.println(System.currentTimeMillis() - start);
    }
}

7. Взаимная рекурсия

Когда метод A вызывает метод B, а метод B вызывает метод A:

public class MutualRecursion {
    public static boolean isEven(int n) {
        if (n == 0) {
            return true;  // Базовый случай
        }
        return isOdd(n - 1);  // Вызываем isOdd
    }
    
    public static boolean isOdd(int n) {
        if (n == 0) {
            return false;  // Базовый случай
        }
        return isEven(n - 1);  // Вызываем isEven
    }
    
    public static void main(String[] args) {
        System.out.println(isEven(4));  // true
        System.out.println(isOdd(5));   // true
    }
}

8. Хвостовая рекурсия (Tail Recursion)

Оптимизируемая форма рекурсии:

public class TailRecursion {
    // Обычная рекурсия (не хвостовая)
    public static int sum(int n) {
        if (n <= 0) {
            return 0;
        }
        return n + sum(n - 1);  // Есть операция ПОСЛЕ вызова
    }
    
    // Хвостовая рекурсия (может быть оптимизирована)
    public static int tailSum(int n, int accumulator) {
        if (n <= 0) {
            return accumulator;  // Базовый случай
        }
        return tailSum(n - 1, accumulator + n);  // Вызов в конце
    }
    
    public static void main(String[] args) {
        System.out.println(sum(100));        // Может вызвать overflow
        System.out.println(tailSum(100, 0)); // Более эффективна
    }
}

Практический пример: обход директорий

import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class DirectoryTraversal {
    public static List<String> findAllFiles(File directory) {
        List<String> files = new ArrayList<>();
        
        if (!directory.isDirectory()) {
            return files;  // Базовый случай
        }
        
        File[] fileList = directory.listFiles();
        if (fileList != null) {
            for (File file : fileList) {
                if (file.isFile()) {
                    files.add(file.getAbsolutePath());
                } else if (file.isDirectory()) {
                    // Рекурсивно обходим подпапки
                    files.addAll(findAllFiles(file));
                }
            }
        }
        
        return files;
    }
    
    public static void main(String[] args) {
        List<String> allFiles = findAllFiles(new File("."));
        allFiles.forEach(System.out::println);
    }
}

Когда использовать рекурсию

Заключение

Рекурсия — это когда метод вызывает сам себя. Это мощный инструмент для работы с рекурсивными структурами (деревья, графы, файловая система). Ключ — всегда иметь базовый случай, чтобы избежать бесконечной рекурсии и переполнения стека. Для оптимизации используйте мемоизацию и хвостовую рекурсию.