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

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

Рекурсивные функции

«Основы рекурсии» — бесплатный урок 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 уроков всего.

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

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

Две обязательные части

Каждой корректной рекурсивной функции нужны:

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

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

Факториал

Классический пример: n! = n * (n-1)!, где 0! = 1 — базовый случай.

object Main {
  def factorial(n: Int): Int =
    if (n <= 1) 1
    else n * factorial(n - 1)

  def main(args: Array[String]): Unit = {
    println(factorial(5))
  }
}

Отслеживание вызовов

Каждый рекурсивный вызов приостанавливается и ждёт внутреннего результата. factorial(3) раскрывается в 3 * (2 * (1)). Умножения выполняются по мере возврата из вызовов.

object Main {
  def factorial(n: Int): Int = {
    println(s"entering factorial($n)")
    if (n <= 1) 1 else n * factorial(n - 1)
  }

  def main(args: Array[String]): Unit = {
    println("result = " + factorial(3))
  }
}

Сумма списка

Рекурсия для списка: сумма равна его голове плюс сумма хвоста, а сумма пустого списка равна нулю.

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

  def main(args: Array[String]): Unit = {
    println(sum(List(1, 2, 3, 4)))
  }
}

Длина списка

Та же схема вычисляет длину: для пустого списка результат равен 0, в противном случае — 1 плюс длина хвоста.

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

  def main(args: Array[String]): Unit = {
    println(length(List("a", "b", "c")))
  }
}

Стек вызовов

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

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

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

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

  def main(args: Array[String]): Unit = {
    println(fib(10))
  }
}

Разворот списка

Рекурсия может строить новые структуры: reverse добавляет голову после разворота хвоста.

object Main {
  def reverse[A](xs: List[A]): List[A] = xs match {
    case Nil    => Nil
    case h :: t => reverse(t) :+ h
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3)))
  }
}

Рекурсия и итерация

Циклы изменяют счётчик, а рекурсия выражает задачу декларативно. Оба подхода допустимы. Рекурсия особенно удобна для древовидных данных и подхода «разделяй и властвуй», но наивная рекурсия может переполнить стек на больших линейных входных данных.

Наибольший общий делитель

Алгоритм Евклида естественным образом выражается рекурсивно и быстро сходится.

object Main {
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(48, 18))
  }
}

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

Проверьте основы рекурсии.

Итоги

Вы изучили основы рекурсии:

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

Далее Вы научитесь делать рекурсию безопасной для стека с помощью аннотации @tailrec.

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

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

Да — полный текст урока «Основы рекурсии» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 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