Рекурсия

Под рекурсией понимается способность функции вызывать саму себя. Достаточно просто, верно? Данная методика делит решаемую программистом проблему на мелкие кусочки (принцип "Разделяй и властвуй"), решения которых возвращаются в основную функцию, и в конце концов соединяются в общую цепь решения.

Из раздела Википедии, посвященному принципу "Разделяй и властвуй":

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

Но существуют и некорректные способы использования рекурсии. На самом деле, любую проблему, которую вы можете решить рекурсией, вы также можете решить, используя ваши любимые итераторы. И если вы ловите себя на мысли "почему бы здесь просто не использовать while", то, скорее всего, вам так и следует поступить. Не следует часто прибегать к рекурсии -- вы просто должны понимать, в каких случаях такое решение предпочтительнее. Решение некоторых задач может распадаться на такое огромное число кусочков, что это вызывает излишние затраты памяти компьютера. Вы должны соблюдать разумный баланс.

В этом коротком уроке вы узнаете о том, в каких случаях и как следует использовать рекурсию, а в следующем проекте примените эти знания на практике.

Пункты для размышления

Постарайтесь ответить на предложенные вопросы. После выполнения задания попробуйте ответить на них ещё раз

  • В чем польза рекурсии при решении больших задач?
  • Какие существуют ограничения для использовании рекурсии?
  • Какие задачи лучше решать простыми циклами, а не рекурсией?
  • Что подразумевается под глубиной рекурсии?
  • Что такое "stack overflow" (концепция, а не сайт)?
  • Почему этот термин относится к проблемам, связанными с рекурсией?

Задания

  1. Прочтите главу по рекурсии в бастардской книге Ruby.
  2. Посмотрите это видео по рекурсии от Joshua Cheek, но только до 17:45! (не хочу раскрывать реализацию нашего задания...)
  3. Прочтите раздел "Вопросы реализации", чтобы получить представление о некоторых ограничениях в рекурсии.

Проверьте себя

  1. Выполните тест на codequizzes.com по рекурсии.

Дополнительные ресурсы

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

  • "Что такое рекурсия в Ruby и как это работает?" на Stack Overflow
  • статья об эффективной рекурсии с сайта Университета Альберты
  • блог Natashatherobot о рекурсии в Ruby
  • пост о технике функционального программирования в Ruby, где раскрываются основы рекурсии

Поделиться уроком: