Разработка
Daniil Lebedev

5 основных рекурсивных задач на собеседованиях по программированию

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

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

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

Быстрый DFS

Задача: имеется двоичное дерево с несколькими узлами. С помощью алгоритма DFS напишите программу для печати значений всех имеющихся узлов. Порядок не имеет значения.

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

class Node { constructor(value) { this.value = value; } } let root = new Node(10); root.left = new Node(5); root.left.left = new Node(2); root.left.right = new Node(1); root.right = new Node(12); root.right.left = new Node(42); root.right.right = new Node(16); dfs(root); function dfs(root) { if(root) { // Print value console.log(root.value); // Traverse left sub-tree dfs(root.left); // Traverse right sub-tree dfs(root.right); } }

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

Магическая функция

Задача: функция max (int x, int y) возвращает наибольшее целое число в интервале между x и y. Если есть некоторое другое целое число, тогда мы можем записать оператор в однострочном формате, например max (int x, max (int x, int y)). Напишите функцию для вывода N переменных в однострочном формате.

Решение: записывая ответы для нескольких входных значений, например 2, 3 и 4, заметим, что второй параметр является рекурсивным. Другими словами, область int y рекурсивно определяет функцию main. В отличие от предыдущего случая, чтобы получить окончательный ответ, эта задача требует сбора ответов от всех подзадач.

function magic(n) { if(n <= 0) return "int y"; return "max(int x, " + magic(n - 1) + ")" } let N = 5; console.log(magic(N));

Рекурсивное суммирование

Задача: напишите рекурсивную функцию для вычисления суммы заданных положительных целых чисел a и b без прямого использования оператора +.

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

function sum(a, b) { if(b == 0) return a; return sum(a + 1, b - 1); } console.log(sum(5, 2));

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

Нахождение максимального значения

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

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

Такой рекурсивный подход поможет легко определить правую часть массива.

function arrayMax(A, i, n) { if(n == 1) return A[0]; return Math.max(A[i], arrayMax(A, i + 1, n - 1)); } let A = [4, 6, 5, 44, 2]; console.log(arrayMax(A, 0, A.length));

Связанный список

Задача: напишите рекурсивную функцию для печати всех значений связанного списка.

Решение: оно очень похоже на алгоритм DFS с двоичным деревом:

class Node { constructor(value) { this.value = value; } } let head = new Node(10); head.next = new Node(5); head.next.next = new Node(2); head.next.next.next = new Node(12); displayNode(head); function displayNode(head) { if(head) { console.log(head.value); displayNode(head.next); } }

На собеседованиях я обычно даю эту задачу вместе с теоретическими вопросами об односвязном списке.

В завершении статьи хочу сказать, что еще больше полезной и нужной информации вы найдете в нашем Telegram-канале. Подпишитесь, мне будет очень приятно.

Оригинал данной статьи на английском:Shalitha Suranga: Top 5 Problems to Test Your Recursion Knowledge for Your Next Coding Interview

99 показов
7.8K открытий
0
1 комментарий
John Snow

There is more concise version of arrayMax

function arrayMax(arr) {
if(arr.length == 1) {
return arr[0];
}

const pivot = arr.length/2;

const left = arrayMax(arr.slice(0, pivot));
const right = arrayMax(arr.slice(pivot));

return left > right ? left : right
}

Ответить
Развернуть ветку
Написать комментарий...
-2 комментариев
Раскрывать всегда