Рекурсия

Рекурсия — мощный инструмент программирования, позволяющий функциям вызывать сами себя для решения задач. Это элегантный способ решать проблемы, которые можно разбить на более простые подзадачи того же типа. В этой статье мы рассмотрим принципы работы рекурсии, её реализацию в Dart, типичные примеры использования и методы оптимизации.

Основы рекурсии

Рекурсивная функция состоит из двух основных частей:

1. Базовый случай — условие выхода из рекурсии
2. Рекурсивный случай — вызов функцией самой себя с измененными параметрами

Без базового случая (условия выхода) функция будет вызывать себя бесконечно, что приведет к переполнению стека.

void recursiveFunction(int n) {
  // Базовый случай
  if (n <= 0) {
    print('Достигнут базовый случай');
    return;
  }
 
  // Рекурсивный случай
  print('Рекурсивный вызов с n = $n');
  recursiveFunction(n - 1);
}

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

Факториал

Факториал числа n (обозначается n!) — произведение всех положительных целых чисел от 1 до n. Это классический пример для иллюстрации рекурсии.

int factorial(int n) {
  // Базовый случай, условие выхода
  if (n <= 1) {
    return 1;
  }
 
  // Рекурсивный случай
  return n * factorial(n - 1);
}
 
void main() {
  print('5! = ${factorial(5)}'); // Выведет: 5! = 120
}

Числа Фибоначчи

Последовательность Фибоначчи определяется рекурсивно: каждое число равно сумме двух предыдущих (начиная с 0 и 1).

int fibonacci(int n) {
  // Базовые случаи
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
 
  // Рекурсивный случай
  return fibonacci(n - 1) + fibonacci(n - 2);
}
 
void main() {
  print('Число Фибоначчи #6: ${fibonacci(6)}'); // Выведет: Число Фибоначчи #6: 8
}

Проблемы и ограничения рекурсии

Переполнение стека

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

void infiniteRecursion() {
  infiniteRecursion(); // Вызовет Stack Overflow
}

Дублирование вычислений

В наивной реализации некоторых рекурсивных алгоритмов (например, Фибоначчи) одни и те же значения вычисляются многократно, что существенно снижает производительность.

Оптимизация рекурсивных функций

Хвостовая рекурсия

Хвостовая рекурсия — это форма рекурсии, где рекурсивный вызов является последней операцией в функции. Она может быть оптимизирована компилятором, хотя в Dart такая оптимизация встроена не всегда.

int factorialTailRecursive(int n, [int accumulator = 1]) {
  if (n <= 1) {
    return accumulator;
  }
 
  return factorialTailRecursive(n - 1, n * accumulator);
}
 
void main() {
  print('5! = ${factorialTailRecursive(5)}'); // Выведет: 5! = 120
}

Практические примеры рекурсии в Dart

Вычисление наибольшего общего делителя (алгоритм Евклида)

int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
 
  return gcd(b, a % b);
}

Домашнее задание

Задачи на закрепление материала по рекурсии в Dart.

1. Сумма цифр числа

Задача: Написать рекурсивную функцию, которая принимает целое число и возвращает сумму его цифр.

sumDigits(123) -> 6
sumDigits(4567) -> 22

2. Разворот строки

Задача: Написать рекурсивную функцию, которая принимает строку и возвращает её в обратном порядке.

reverseString("hello") -> "olleh"
reverseString("dart") -> "trad"

3. Генерация перестановок строки

Задача: Написать рекурсивную функцию, которая генерирует все возможные перестановки символов в заданной строке.

generatePermutations("abc") -> ["abc", "acb", "bac", "bca", "cab", "cba"]

4. Ханойские башни

Задача: Написать рекурсивную функцию для решения головоломки "Ханойские башни". Функция должна принимать количество дисков и выводить последовательность перемещений дисков.

hanoiTowers(3, 'A', 'C', 'B') ->
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C