Scala for Backend Engineering & Functional Programming · Урок

Рекурсивное мышление

Базовые случаи и рекурсивные шаги.

Урок 1 из 413 шагов

«Рекурсивное мышление» — бесплатный урок Scala for Backend Engineering & Functional Programming на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Scala for Backend Engineering & Functional Programming, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Что такое рекурсия

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

В Scala рекурсия естественно подходит для функционального программирования, поскольку позволяет выражать циклы без изменяемых переменных.

Каждой рекурсивной функции нужны две вещи: способ остановиться и способ уменьшать задачу.

Сначала базовый случай

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

Без базового случая функция вызывала бы сама себя бесконечно и завершилась бы переполнением стека.

Всегда проектируйте базовый случай до рекурсивного шага.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Первая рекурсивная функция

Вот полная программа, которая суммирует числа от 1 до n.

Базовый случай возвращает 0, а рекурсивный случай прибавляет n к сумме всех чисел меньше него.

def sum(n: Int): Int =
  if (n == 0) 0
  else n + sum(n - 1)

@main def run(): Unit =
  println(sum(5))   // 15

Трассировка вызовов

Чтобы понять рекурсию, разверните вызовы вручную.

sum(3) превращается в 3 + sum(2), затем в 3 + 2 + sum(1), а затем в 3 + 2 + 1 + sum(0).

Только после того, как sum(0) вернёт 0, цепочка сворачивается обратно в одно значение: 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Рекурсия для списков

Списки рекурсивны по своей природе: список либо пуст, либо состоит из головы и хвоста меньшего размера.

Такая структура напрямую отображается на рекурсивные функции. Пустой список — базовый случай, а голова плюс рекурсия для хвоста — рекурсивный шаг.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Сопоставление хвоста с шаблоном

Шаблон :: разделяет непустой список на голову и хвост.

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

Это стандартный способ рекурсивного прохода по списку в Scala.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Два рекурсивных вызова

Некоторые задачи разветвляются на несколько рекурсивных вызовов.

Классический пример — последовательность Фибоначчи, где каждое значение зависит от двух предыдущих.

Эта наивная версия проста, но медленна, поскольку многократно вычисляет одни и те же значения.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Цена для стека

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

При очень глубокой рекурсии стек может закончиться, и будет выброшена ошибка StackOverflowError.

Подсчёт глубины, а не только размера входных данных, помогает предсказать этот риск.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Движение к базовому случаю

Главный инвариант рекурсии заключается в том, что каждый вызов должен приближать нас к базовому случаю.

Если аргумент не уменьшается или условие остановки никогда не достигается, рекурсия не завершится.

Проверьте это до запуска программы.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Рекурсия и циклы

Императивный код использует циклы while с изменяемыми счётчиками, а функциональный код — рекурсию с неизменяемыми значениями.

Оба подхода могут выражать одни и те же вычисления, но рекурсия более непосредственно описывает структуру данных.

В Scala Вы часто будете предпочитать рекурсию или функции высшего порядка обычным циклам.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Проектирование рекурсивного решения

Надёжный алгоритм таков: определите базовый случай, предположите, что рекурсивный вызов уже работает с меньшими входными данными, а затем объедините голову с полученным результатом.

Этот прыжок веры — основа рекурсивного мышления. Вы доверяете меньшему вызову и обрабатываете только один шаг.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Быстрая проверка

Проверьте своё понимание рекурсивной структуры.

Ответь в интерактивном уроке

Итоги

Рекурсия решает задачу, сводя её к меньшему экземпляру самой себя.

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

Списки с их структурой из пустого списка, головы и хвоста — идеальная среда для изучения рекурсивного мышления. Следите за глубиной стека при работе с очень большими входными данными.

Можно начать бесплатно

Изучай Scala с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы: 39
Уроки: 143

Начать учиться бесплатно Посмотреть полный курс

Часто задаваемые вопросы

Урок «Рекурсивное мышление» бесплатный?

Да — полный текст урока «Рекурсивное мышление» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Scala for Backend Engineering & Functional Programming, подпишись на CoddyKit PRO. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Чему я научусь в уроке «Рекурсивное мышление»?

Базовые случаи и рекурсивные шаги. Ты практикуешь Scala for Backend Engineering & Functional Programming с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Scala for Backend Engineering & Functional Programming?

Предыдущий опыт не требуется. Scala for Backend Engineering & Functional Programming на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Рекурсивное мышление»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Scala for Backend Engineering & Functional Programming?

Да. Каждый урок Scala for Backend Engineering & Functional Programming включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Scala for Backend Engineering & Functional Programming