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);
    }
}

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

Читайте также:

• Лучшие JavaScript-фреймворки и тенденции веб-разработки в 2021 году
• Аспектно-ориентированное программирование в JavaScript
• Три функции JavaScript для освоения метода Reduce

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Shalitha Suranga: Top 5 Problems to Test Your Recursion Knowledge for Your Next Coding Interview