Рекурсия — один из самых красивых и мощных концептов в программировании. Откройте для себя элегантность рекурсии в Топазе! 🌀
🌱 Основы рекурсии
Что такое рекурсия?
Рекурсия — это техника программирования, при которой функция вызывает саму себя. Она решает сложные задачи, разбивая их на более мелкие идентичные подзадачи.
// Простейшая рекурсия - факториал
function факториал(число: int) -> int {
match число {
case 0 | 1 => 1 // Базовый случай
case _ => число * факториал(число - 1) // Рекурсивный вызов
}
} test {
assert факториал(0) == 1
assert факториал(1) == 1
assert факториал(5) == 120
assert факториал(10) == 3628800
}
// Последовательность Фибоначчи
function фибоначчи(число: int) -> int {
match число {
case 0 => 0
case 1 => 1
case _ => фибоначчи(число - 1) + фибоначчи(число - 2)
}
} test {
assert фибоначчи(0) == 0
assert фибоначчи(1) == 1
assert фибоначчи(8) == 21
assert фибоначчи(12) == 144
}
print("факториал(5) = {факториал(5)}")
print("фибоначчи(8) = {фибоначчи(8)}")Основные элементы рекурсии
- Базовый случай: Условие, останавливающее рекурсию
- Рекурсивное отношение: Часть, которая вызывает сама себя
- Сходимость: Должна в конечном итоге достичь базового случая
🎨 Различные паттерны рекурсии
Линейная рекурсия
// Сумма элементов массива
function суммаМассива(массив: Array<int>, индекс: int = 0) -> int {
if индекс >= массив.length {
return 0
}
return массив[индекс] + суммаМассива(массив, индекс + 1)
}
// Обращение строки
function обратитьСтроку(строка: string) -> string {
if строка.length <= 1 {
return строка
}
let первыйСимвол = строка.charAt(0)
let остаток = строка.substring(1)
return обратитьСтроку(остаток) + первыйСимвол
}
// Наибольший общий делитель (алгоритм Евклида)
function НОД(а: int, б: int) -> int {
match б {
case 0 => а
case _ => НОД(б, а % б)
}
} test {
let числа = [1, 2, 3, 4, 5]
assert суммаМассива(числа) == 15
assert обратитьСтроку("привет") == "тевирп"
assert обратитьСтроку("Топаз") == "zapoT"
assert НОД(48, 18) == 6
assert НОД(100, 25) == 25
}
print("Сумма массива: {суммаМассива([1, 2, 3, 4, 5])}")
print("Обращение строки: {обратитьСтроку("Привет Мир")}")
print("НОД(48, 18): {НОД(48, 18)}")Разделяй и властвуй
// Бинарный поиск
function бинарныйПоиск<T>(
массив: Array<T>,
цель: T,
начало: int = 0,
конец: int = -1
) -> Option<int>
where
T: PartialOrd + PartialEq
{
let реальныйКонец = if конец == -1 { массив.length - 1 } else { конец }
if начало > реальныйКонец {
return None
}
let середина = (начало + реальныйКонец) / 2
match массив[середина] {
case x if x == цель => Some(середина)
case x if x > цель => бинарныйПоиск(массив, цель, начало, середина - 1)
case _ => бинарныйПоиск(массив, цель, середина + 1, реальныйКонец)
}
}
// Сортировка слиянием
function сортировкаСлиянием(массив: Array<int>) -> Array<int> {
if массив.length <= 1 {
return массив
}
let середина = массив.length / 2
let левая = массив[0..середина].to_vec()
let правая = массив[середина..].to_vec()
let отсортированнаяЛевая = сортировкаСлиянием(левая)
let отсортированнаяПравая = сортировкаСлиянием(правая)
return слить(отсортированнаяЛевая, отсортированнаяПравая)
}
function слить(левая: Array<int>, правая: Array<int>) -> Array<int> {
let mut результат: Array<int> = []
let mut и = 0
let mut д = 0
while и < левая.length && д < правая.length {
if левая[и] <= правая[д] {
результат.push(левая[и])
и += 1
} else {
результат.push(правая[д])
д += 1
}
}
// Добавить оставшиеся элементы
результат.extend(&левая[и..])
результат.extend(&правая[д..])
return результат
}
// Быстрая сортировка
function быстраяСортировка(массив: Array<int>) -> Array<int> {
if массив.length <= 1 {
return массив
}
let опорный = массив[массив.length / 2]
let меньшие = массив.filter(|&x| x < опорный)
let равные = массив.filter(|&x| x == опорный)
let большие = массив.filter(|&x| x > опорный)
return [
...быстраяСортировка(меньшие),
...равные,
...быстраяСортировка(большие)
]
} test {
let отсортированныйМассив = [1, 3, 5, 7, 9, 11, 13]
assert бинарныйПоиск(отсортированныйМассив, 7) == Some(3)
assert бинарныйПоиск(отсортированныйМассив, 14) == None
let случайныйМассив = [64, 34, 25, 12, 22, 11, 90]
let результатСортировки1 = сортировкаСлиянием(случайныйМассив.clone())
let результатСортировки2 = быстраяСортировка(случайныйМассив.clone())
assert результатСортировки1 == [11, 12, 22, 25, 34, 64, 90]
assert результатСортировки2 == [11, 12, 22, 25, 34, 64, 90]
}
print("Результат бинарного поиска: {бинарныйПоиск([1, 3, 5, 7, 9], 5)}")
print("Сортировка слиянием: {сортировкаСлиянием([3, 1, 4, 1, 5, 9])}")
print("Быстрая сортировка: {быстраяСортировка([3, 1, 4, 1, 5, 9])}")Древовидная рекурсия
// Структура бинарного дерева
enum БинарноеДерево<T> {
Пустое,
Узел {
значение: T,
левый: Box<БинарноеДерево<T>>,
правый: Box<БинарноеДерево<T>>
}
}
impl<T> БинарноеДерево<T>
where
T: Clone + std::fmt::Display + PartialOrd
{
function новыйУзел(значение: T) -> БинарноеДерево<T> {
return БинарноеДерево::Узел {
значение,
левый: Box::new(БинарноеДерево::Пустое),
правый: Box::new(БинарноеДерево::Пустое)
}
}
// Вставить значение в дерево
function вставить(&mut self, новоеЗначение: T) {
match self {
case БинарноеДерево::Пустое => {
*self = БинарноеДерево::новыйУзел(новоеЗначение)
}
case БинарноеДерево::Узел { значение, левый, правый } => {
if новоеЗначение <= *значение {
левый.вставить(новоеЗначение)
} else {
правый.вставить(новоеЗначение)
}
}
}
}
// Поиск в дереве
function найти(&self, цель: &T) -> bool {
match self {
case БинарноеДерево::Пустое => false
case БинарноеДерево::Узел { значение, левый, правый } => {
if цель == значение {
return true
} else if цель < значение {
return левый.найти(цель)
} else {
return правый.найти(цель)
}
}
}
}
// Симметричный обход
function симметричныйОбход(&self) -> Array<T> {
match self {
case БинарноеДерево::Пустое => []
case БинарноеДерево::Узел { значение, левый, правый } => {
let mut результат = левый.симметричныйОбход()
результат.push(значение.clone())
результат.extend(правый.симметричныйОбход())
return результат
}
}
}
// Вычислить высоту дерева
function высота(&self) -> int {
match self {
case БинарноеДерево::Пустое => 0
case БинарноеДерево::Узел { левый, правый, .. } => {
let высотаЛевого = левый.высота()
let высотаПравого = правый.высота()
return 1 + std::cmp::max(высотаЛевого, высотаПравого)
}
}
}
// Подсчет узлов
function количествоУзлов(&self) -> int {
match self {
case БинарноеДерево::Пустое => 0
case БинарноеДерево::Узел { левый, правый, .. } => {
return 1 + левый.количествоУзлов() + правый.количествоУзлов()
}
}
}
} test {
let mut дерево = БинарноеДерево::Пустое
// Вставка значений
let значения = [5, 3, 7, 1, 9, 4, 6]
for значение in значения {
дерево.вставить(значение)
}
// Тесты поиска
assert дерево.найти(&5) == true
assert дерево.найти(&10) == false
// Симметричный обход (отсортированный порядок)
let результатОбхода = дерево.симметричныйОбход()
assert результатОбхода == [1, 3, 4, 5, 6, 7, 9]
// Свойства дерева
assert дерево.высота() == 4
assert дерево.количествоУзлов() == 7
}
// Пример использования
let mut моёДерево = БинарноеДерево::Пустое
[15, 10, 20, 8, 12, 16, 25].iter().for_each(|&значение| моёДерево.вставить(значение))
print("Симметричный обход дерева: {моёДерево.симметричныйОбход()}")
print("Высота дерева: {моёДерево.высота()}")
print("Количество узлов: {моёДерево.количествоУзлов()}")
print("Поиск 15: {моёДерево.найти(&15)}")⚡ Техники оптимизации рекурсии
Хвостовая рекурсия
// Сравнение обычной рекурсии и хвостовой рекурсии
// Обычная рекурсия - риск переполнения стека
function факториал_обычная(число: int) -> int {
if число <= 1 {
return 1
}
return число * факториал_обычная(число - 1) // Умножение после рекурсивного вызова
}
// Хвостовая рекурсия - оптимизируемая
function факториал_хвостовая(число: int, аккумулятор: int = 1) -> int {
if число <= 1 {
return аккумулятор
}
return факториал_хвостовая(число - 1, аккумулятор * число) // Рекурсивный вызов последняя операция
}
// Фибоначчи с хвостовой рекурсией
function фибоначчи_хвостовая(число: int, а: int = 0, б: int = 1) -> int {
match число {
case 0 => а
case 1 => б
case _ => фибоначчи_хвостовая(число - 1, б, а + б)
}
}
// Обращение списка с хвостовой рекурсией
function обратить_хвостовая<T>(
исходный: Array<T>,
результат: Array<T> = [],
индекс: int = 0
) -> Array<T> {
if индекс >= исходный.length {
return результат
}
let mut новыйРезультат = [исходный[индекс]].to_vec()
новыйРезультат.extend(результат)
return обратить_хвостовая(исходный, новыйРезультат, индекс + 1)
}
// Возведение в степень с хвостовой рекурсией
function степень_хвостовая(основание: int, показатель: int, аккумулятор: int = 1) -> int {
match показатель {
case 0 => аккумулятор
case показ if показ % 2 == 0 => степень_хвостовая(основание * основание, показ / 2, аккумулятор)
case показ => степень_хвостовая(основание, показ - 1, аккумулятор * основание)
}
} test {
// Тесты сравнения производительности
assert факториал_обычная(10) == факториал_хвостовая(10)
assert фибоначчи_хвостовая(10) == 55
let исходныйСписок = [1, 2, 3, 4, 5]
let обращённыйСписок = обратить_хвостовая(исходныйСписок)
assert обращённыйСписок == [5, 4, 3, 2, 1]
assert степень_хвостовая(2, 10) == 1024
assert степень_хвостовая(3, 4) == 81
}
print("Хвостовая рекурсия факториал(10): {факториал_хвостовая(10)}")
print("Хвостовая рекурсия фибоначчи(15): {фибоначчи_хвостовая(15)}")
print("Степень 2^10: {степень_хвостовая(2, 10)}")Мемоизация
use std::collections::HashMap
// Структура-обёртка для мемоизации
struct Мемоизация<K, V>
where
K: Clone + std::hash::Hash + Eq,
V: Clone
{
кэш: HashMap<K, V>,
функция: fn(K, &mut Мемоизация<K, V>) -> V
}
impl<K, V> Мемоизация<K, V>
where
K: Clone + std::hash::Hash + Eq,
V: Clone
{
function новая(функция: fn(K, &mut Мемоизация<K, V>) -> V) -> Self {
return Мемоизация {
кэш: HashMap::new(),
функция
}
}
function вызвать(&mut self, аргумент: K) -> V {
match self.кэш.get(&аргумент) { case Some(результат) => return результат.clone(), case None => {} }
let результат = (self.функция)(аргумент.clone(), self)
self.кэш.insert(аргумент, результат.clone())
return результат
}
}
// Мемоизированный фибоначчи
function фибоначчи_мемо_функция(число: int, мемо: &mut Мемоизация<int, int>) -> int {
match число {
case 0 => 0
case 1 => 1
case _ => мемо.вызвать(число - 1) + мемо.вызвать(число - 2)
}
}
// Мемоизация вычисления сочетаний (nCr)
function сочетания_мемо_функция(
параметры: (int, int),
мемо: &mut Мемоизация<(int, int), int>
) -> int {
let (н, к) = параметры
match (н, к) {
case (_, 0) | (н, к) if н == к => 1
case (н, к) if к > н => 0
case (н, к) => {
return мемо.вызвать((н - 1, к - 1)) + мемо.вызвать((н - 1, к))
}
}
}
// Мемоизация наибольшей общей подпоследовательности (НОП)
function НОП_мемо_функция(
параметры: (string, string),
мемо: &mut Мемоизация<(string, string), int>
) -> int {
let (строка1, строка2) = параметры
if строка1.is_empty() || строка2.is_empty() {
return 0
}
if строка1.chars().last() == строка2.chars().last() {
let префикс1 = &строка1[..строка1.len() - 1]
let префикс2 = &строка2[..строка2.len() - 1]
return 1 + мемо.вызвать((префикс1.to_string(), префикс2.to_string()))
} else {
let префикс1 = &строка1[..строка1.len() - 1]
let префикс2 = &строка2[..строка2.len() - 1]
let случай1 = мемо.вызвать((строка1.clone(), префикс2.to_string()))
let случай2 = мемо.вызвать((префикс1.to_string(), строка2.clone()))
return std::cmp::max(случай1, случай2)
}
} test {
// Тест мемоизации фибоначчи
let mut фибоначчиМемо = Мемоизация::новая(фибоначчи_мемо_функция)
assert фибоначчиМемо.вызвать(10) == 55
assert фибоначчиМемо.вызвать(20) == 6765
// Тест мемоизации сочетаний
let mut сочетанияМемо = Мемоизация::новая(сочетания_мемо_функция)
assert сочетанияМемо.вызвать((5, 2)) == 10
assert сочетанияМемо.вызвать((10, 3)) == 120
// Тест мемоизации НОП
let mut НОПМемо = Мемоизация::новая(НОП_мемо_функция)
let результат = НОПМемо.вызвать(("АБВГДЕ".to_string(), "АЕГЖЗИ".to_string()))
assert результат == 3 // "АЕГ"
}
// Пример использования
let mut фибоначчиМемо = Мемоизация::новая(фибоначчи_мемо_функция)
print("Мемоизированный фибоначчи(30): {фибоначчиМемо.вызвать(30)}")
let mut сочетанияМемо = Мемоизация::новая(сочетания_мемо_функция)
print("Сочетания C(20, 10): {сочетанияМемо.вызвать((20, 10))}")🎯 Практические применения рекурсии
Возврат (Backtracking)
// Задача N ферзей
function решитьНФерзей(н: int) -> Array<Array<int>> {
let mut решения: Array<Array<int>> = []
let mut текущееРешение: Array<int> = vec![0; н]
function возврат(ряд: int) {
if ряд == н {
решения.push(текущееРешение.clone())
return
}
for столбец in 0..н {
if безопаснаяПозиция(ряд, столбец, &текущееРешение) {
текущееРешение[ряд] = столбец
возврат(ряд + 1)
// Возврат: автоматически восстанавливает предыдущее состояние
}
}
}
function безопаснаяПозиция(ряд: int, столбец: int, решение: &Array<int>) -> bool {
for предыдущийРяд in 0..ряд {
let предыдущийСтолбец = решение[предыдущийРяд]
// Проверить тот же столбец
if предыдущийСтолбец == столбец {
return false
}
// Проверить диагонали
if (предыдущийРяд - ряд).abs() == (предыдущийСтолбец as int - столбец as int).abs() {
return false
}
}
return true
}
возврат(0)
return решения
}
// Поиск выхода из лабиринта
struct Лабиринт {
сетка: Array<Array<bool>>, // true = путь, false = стена
высота: int,
ширина: int
}
impl Лабиринт {
function новый(сетка: Array<Array<bool>>) -> Лабиринт {
let высота = сетка.len() as int
let ширина = if высота > 0 { сетка[0].len() as int } else { 0 }
return Лабиринт { сетка, высота, ширина }
}
function найтиПуть(&self) -> Option<Array<(int, int)>> {
let mut посещённые: Array<Array<bool>> = vec![vec![false; self.ширина as usize]; self.высота as usize]
let mut путь: Array<(int, int)> = []
if self.DFS(0, 0, &mut посещённые, &mut путь) {
return Some(путь)
} else {
return None
}
}
function DFS(
&self,
ряд: int,
столбец: int,
посещённые: &mut Array<Array<bool>>,
путь: &mut Array<(int, int)>
) -> bool {
// Проверка границ
if ряд < 0 || ряд >= self.высота || столбец < 0 || столбец >= self.ширина {
return false
}
// Стена или уже посещено
if !self.сетка[ряд as usize][столбец as usize] || посещённые[ряд as usize][столбец as usize] {
return false
}
// Добавить текущую позицию в путь
путь.push((ряд, столбец))
посещённые[ряд as usize][столбец as usize] = true
// Достигли пункта назначения
if ряд == self.высота - 1 && столбец == self.ширина - 1 {
return true
}
// Исследовать 4 направления
let направления = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for (др, дс) in направления {
if self.DFS(ряд + др, столбец + дс, посещённые, путь) {
return true
}
}
// Возврат: удалить из пути
путь.pop()
посещённые[ряд as usize][столбец as usize] = false
return false
}
} test {
// Тест задачи 4 ферзей
let решения = решитьНФерзей(4)
assert решения.len() == 2 // У 4x4 есть 2 решения
// Тест лабиринта
let сеткаЛабиринта = [
[true, false, true, true],
[true, true, false, true],
[false, true, true, true],
[false, false, false, true]
]
let мойЛабиринт = Лабиринт::новый(сеткаЛабиринта.map(|ряд| ряд.to_vec()).to_vec())
let путь = мойЛабиринт.найтиПуть()
assert путь.is_some()
}
// Пример использования
let решения = решитьНФерзей(8) // Задача 8 ферзей
print("Количество решений 8 ферзей: {решения.len()}")
match решения.first() { case Some(первоеРешение) => print("Первое решение: {первоеРешение:?}"), case None => {} }Динамическое программирование с рекурсией
// Задача о рюкзаке
struct Предмет {
вес: int,
ценность: int,
название: string
}
function рюкзак_рекурсивно(
предметы: &Array<Предмет>,
вместимость: int,
индекс: int = 0
) -> int {
// Базовое условие
if индекс >= предметы.len() || вместимость <= 0 {
return 0
}
let текущийПредмет = &предметы[индекс]
// Не можем включить текущий предмет
if текущийПредмет.вес > вместимость {
return рюкзак_рекурсивно(предметы, вместимость, индекс + 1)
}
// Выбрать максимум из двух вариантов
let включитьСлучай = текущийПредмет.ценность + рюкзак_рекурсивно(
предметы,
вместимость - текущийПредмет.вес,
индекс + 1
)
let исключитьСлучай = рюкзак_рекурсивно(предметы, вместимость, индекс + 1)
return std::cmp::max(включитьСлучай, исключитьСлучай)
}
// Расстояние редактирования
function расстояниеРедактирования_рекурсивно(строка1: &str, строка2: &str) -> int {
if строка1.is_empty() {
return строка2.len() as int
}
if строка2.is_empty() {
return строка1.len() as int
}
let символы1: Vec<char> = строка1.chars().collect()
let символы2: Vec<char> = строка2.chars().collect()
if символы1.last() == символы2.last() {
let префикс1: String = символы1[..символы1.len()-1].iter().collect()
let префикс2: String = символы2[..символы2.len()-1].iter().collect()
return расстояниеРедактирования_рекурсивно(&префикс1, &префикс2)
}
let префикс1: String = символы1[..символы1.len()-1].iter().collect()
let префикс2: String = символы2[..символы2.len()-1].iter().collect()
let вставить = 1 + расстояниеРедактирования_рекурсивно(строка1, &префикс2)
let удалить = 1 + расстояниеРедактирования_рекурсивно(&префикс1, строка2)
let заменить = 1 + расстояниеРедактирования_рекурсивно(&префикс1, &префикс2)
return std::cmp::min(вставить, std::cmp::min(удалить, заменить))
}
// Задача подъёма по ступенькам
function подъёмПоСтупенькам(число: int) -> int {
match число {
case 0 => 1
case 1 => 1
case 2 => 2
case _ => подъёмПоСтупенькам(число - 1) + подъёмПоСтупенькам(число - 2)
}
} test {
// Тест задачи о рюкзаке
let предметы = [
Предмет { вес: 10, ценность: 60, название: "книга".to_string() },
Предмет { вес: 20, ценность: 100, название: "компьютер".to_string() },
Предмет { вес: 30, ценность: 120, название: "телевизор".to_string() }
]
let максЦенность = рюкзак_рекурсивно(&предметы, 50)
assert максЦенность == 220 // книга + компьютер = 60 + 100 + 60 = 220
// Тест расстояния редактирования
assert расстояниеРедактирования_рекурсивно("котёнок", "сидящий") == 8
assert расстояниеРедактирования_рекурсивно("привет", "хорошо") == 6
// Тест подъёма по ступенькам
assert подъёмПоСтупенькам(1) == 1
assert подъёмПоСтупенькам(3) == 3
assert подъёмПоСтупенькам(5) == 8
}
print("Максимальная ценность рюкзака: {рюкзак_рекурсивно(&предметы, 50)}")
print("Расстояние редактирования (привет -> мир): {расстояниеРедактирования_рекурсивно("привет", "мир")}")
print("Способы подъёма на 10 ступенек: {подъёмПоСтупенькам(10)}")🚨 Меры предосторожности при рекурсии
Предотвращение переполнения стека
// Опасная рекурсия - потенциальное переполнение стека
function опаснаяРекурсия(число: int) -> int {
if число <= 0 {
return 0
}
return 1 + опаснаяРекурсия(число - 1) // Переполнение стека для больших n
}
// Безопасная итеративная версия
function безопаснаяИтерация(число: int) -> int {
let mut результат = 0
for и in 1..=число {
результат += 1
}
return результат
}
// Безопасная рекурсия с проверкой переполнения стека
function безопаснаяРекурсия(число: int, глубина: int = 0) -> Result<int, string> {
const МАКС_ГЛУБИНА: int = 1000
if глубина > МАКС_ГЛУБИНА {
return Err("Превышена глубина рекурсии: риск переполнения стека".to_string())
}
if число <= 0 {
return Ok(0)
}
match безопаснаяРекурсия(число - 1, глубина + 1) {
case Ok(результат) => Ok(1 + результат)
case Err(ошибка) => Err(ошибка)
}
}
// Техника батута для предотвращения переполнения стека
enum Батут<T> {
Готово(T),
Продолжить(Box<dyn FnOnce() -> Батут<T>>)
}
function выполнитьБатут<T>(mut результат: Батут<T>) -> T {
loop {
match результат {
case Батут::Готово(значение) => return значение
case Батут::Продолжить(функция) => результат = функция()
}
}
}
function факториал_батут(число: int, аккумулятор: int = 1) -> Батут<int> {
if число <= 1 {
return Батут::Готово(аккумулятор)
}
return Батут::Продолжить(Box::new(move || {
факториал_батут(число - 1, аккумулятор * число)
}))
} test {
// Тест безопасной рекурсии
assert безопаснаяРекурсия(100).is_ok()
assert безопаснаяРекурсия(2000).is_err()
// Тест техники батута
let результат = выполнитьБатут(факториал_батут(10))
assert результат == 3628800
}
print("Безопасная рекурсия (100): {безопаснаяРекурсия(100).unwrap()}")
print("Батут факториал(10): {выполнитьБатут(факториал_батут(10))}")🎨 Функциональные паттерны рекурсии
Функции высшего порядка и рекурсия
// Рекурсивная реализация map
function рекурсивныйMap<T, U>(
массив: Array<T>,
функцияПреобразования: fn(T) -> U,
индекс: int = 0
) -> Array<U> {
if индекс >= массив.len() {
return []
}
let mut результат = [функцияПреобразования(массив[индекс].clone())]
результат.extend(рекурсивныйMap(массив, функцияПреобразования, индекс + 1))
return результат
}
// Рекурсивная реализация filter
function рекурсивныйFilter<T>(
массив: Array<T>,
функцияПредиката: fn(&T) -> bool,
индекс: int = 0
) -> Array<T> {
if индекс >= массив.len() {
return []
}
let текущийЭлемент = &массив[индекс]
let оставшийсяРезультат = рекурсивныйFilter(массив.clone(), функцияПредиката, индекс + 1)
if функцияПредиката(текущийЭлемент) {
let mut результат = [текущийЭлемент.clone()]
результат.extend(оставшийсяРезультат)
return результат
} else {
return оставшийсяРезультат
}
}
// Рекурсивная реализация reduce
function рекурсивныйReduce<T, U>(
массив: Array<T>,
начальноеЗначение: U,
функцияСведения: fn(U, T) -> U,
индекс: int = 0
) -> U {
if индекс >= массив.len() {
return начальноеЗначение
}
let новоеНачальноеЗначение = функцияСведения(начальноеЗначение, массив[индекс].clone())
return рекурсивныйReduce(массив, новоеНачальноеЗначение, функцияСведения, индекс + 1)
}
// Реализация Y-комбинатора
function Y<F, T>(функция: F) -> impl Fn(T) -> T
where
F: Fn(&dyn Fn(T) -> T, T) -> T,
T: 'static
{
move |ввод| {
let рекурсивнаяФункция = |себя: &dyn Fn(T) -> T, параметр: T| -> T {
функция(себя, параметр)
}
рекурсивнаяФункция(&рекурсивнаяФункция, ввод)
}
} test {
let числа = [1, 2, 3, 4, 5]
// Тест рекурсивного map
let квадраты = рекурсивныйMap(числа.clone(), |x| x * x)
assert квадраты == [1, 4, 9, 16, 25]
// Тест рекурсивного filter
let чётные = рекурсивныйFilter(числа.clone(), |&x| x % 2 == 0)
assert чётные == [2, 4]
// Тест рекурсивного reduce
let сумма = рекурсивныйReduce(числа.clone(), 0, |акк, x| акк + x)
assert сумма == 15
}
print("Рекурсивный map (квадраты): {рекурсивныйMap([1, 2, 3, 4], |x| x * x)}")
print("Рекурсивный filter (чётные): {рекурсивныйFilter([1, 2, 3, 4, 5, 6], |&x| x % 2 == 0)}")
print("Рекурсивный reduce (сумма): {рекурсивныйReduce([1, 2, 3, 4, 5], 0, |акк, x| акк + x)}")🎯 Мастерство рекурсии
Рекурсия — мощный инструмент для элегантного решения сложных задач:
✅ Когда использовать рекурсию:
- Обработка древовидных/графовых структур
- Алгоритмы разделяй и властвуй
- Задачи возврата (backtracking)
- Математические определения, которые рекурсивны
⚠️ Меры предосторожности при рекурсии:
- Чётко определить базовые условия
- Предотвратить переполнение стека
- Рассмотреть оптимизацию производительности (мемоизация, хвостовая рекурсия)
- Учесть сложность отладки
🚀 Преимущества рекурсии в Топазе:
- Сопоставление с образцом для чёткого разделения условий
- Типобезопасность для предотвращения ошибок
- Поддержка парадигмы функционального программирования
- Автоматическая оптимизация хвостовой рекурсии
Исследуйте прекрасный мир рекурсии с Топазом! 🌀✨