Инсайдерское руководство по вопросам рекурсивного интервью

Снова и снова вы слышите, как люди говорят: «Рекурсия — это слишком сложно» или «Зачем мне изучать рекурсию, если ее можно решить с помощью итерации?» Простой поиск в Google найдет огромное количество вопросов о том, почему рекурсия так сложна для понимания.

Так зачем изучать рекурсию? Что ж, способность мыслить рекурсивно очень важна в программировании по нескольким причинам:

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

Рекурсия — это фундаментальный стиль решения проблем, и каждый разработчик должен иметь его в своем наборе инструментов. Вы будете удивлены (а может и нет), узнав, как часто рекурсия упоминается на собеседованиях по кодированию, особенно в крупных компаниях, таких как Google, Microsoft и Facebook. Так что, если вы собираетесь на собеседование и чувствуете тошноту по поводу рекурсии, возможно, пришло время освежить ее, и мы вам поможем.

Ищете полный курс по рекурсии для интервью? Начните здесь.

Когда начать

Одна из самых первых программ, которая заставит вас задуматься о рекурсии, — это последовательность Фибоначчи. Давайте ненадолго рассмотрим пример на C++.

{ 
  // base case 
  
  if (n<=1) 
  
  { 
     return n; 
  } 
  
  // recursive case 
  else 
  
  { 
     return (fibonacci(n-1) + fibonacci(n-2))   
  } 
}

Здесь у нас есть рекурсивная функция, состоящая из двух частей; базовый случай и рекурсивный случай. Базовый вариант функции определяется в строке 5, где функция завершится и вернет «n», когда будет выполнено условие «if» n‹=1. Другими словами, базовый вариант — это то, что завершает вашу программу.

Затем идет рекурсивный случай или функция, которую мы хотим повторять, пока не достигнем базового случая. Таким образом, если базовое условие не оценивается как истинное, функция переходит в блок «else» (строки 8–11), где затем рекурсивно вызывает себя с входными аргументами «fibonacci(n- 1)+ фибоначчи(n-2)», как показано в строке 10.

Теперь ваш интервьюер скажет вам что-то вроде: «Верните n-й элемент в ряду Фибоначчи». Итак, вы взяли на себя обязательство использовать традиционный цикл while, и он работает, но эффективен ли он? Поэтому интервьюер спрашивает: «Как бы вы оптимизировали этот алгоритм?» Один из способов сделать это - использовать рекурсию, поскольку у вас есть только две переменные (fibonacci n-1) и (fibonacci n-2). Они могут задать дополнительный вопрос, например: «Как бы вы еще оптимизировали свою рекурсивную функцию?» Один из способов сделать это — использовать запоминание — технику, используемую для ускорения работы компьютерных программ путем сохранения результатов дорогостоящих вызовов функций и возврата кэшированного результата при повторении одних и тех же входных данных.

Что хорошего в этом примере и последовательности Фибоначчи, так это то, что это переход к некоторым очень полезным методам, таким как мемоизация и динамическое программирование.

Всегда думайте о базовом случае

Если вы проходите техническое собеседование и возникает вопрос о рекурсии, всегда лучше начать с конца или с базового случая. Рекурсивная функция состоит из двух частей;

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

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

Выявление вопросов рекурсии — слушайте ключевые слова

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

Вопросы, которые нужно задать себе

Если вам задают технический вопрос на собеседовании, посвященном рекурсии, важно подумать о нескольких вещах:

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

Концепции рекурсии, к которым вы должны быть готовы

Структуры данных

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

Алгоритмы

Обходы графа, например. Поиск в глубину и поиск в ширину
Быстрая сортировка (следует схеме «разделяй и властвуй») — высокоэффективный алгоритм сортировки, основанный на разбиении массива данных на более мелкие массивы.
Сортировка слиянием (следует схеме «разделяй и властвуй») — список разбивается на несколько подсписков до тех пор, пока каждый подсписок не будет состоять из одного элемента, и объединение этих подсписков таким образом, что в результате получается отсортированный список.
Двоичный поиск — находит положение целевого значения в отсортированном массиве, рекурсивно работая со все меньшим и меньшим массивом, пока вы не найдете значение или размер массива не станет равным 0.

Узоры

Разделяй и властвуй — шаблон, который разбивает проблему на более мелкие подзадачи, которые затем рекурсивно решаются и объединяются (отлично подходит для сортировки по дереву).

Техники

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

Проблемы, которые помогут вам практиковаться

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

Заворачивать

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

Есть несколько вещей, которые вы должны сделать, прежде чем отправиться на собеседование:

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

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

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

Первоначально опубликовано на https://blog.educative.io 16 апреля 2019 г.