Каков наилучший способ спланировать рекурсивное решение проблемы?

Question

Я учусь рекурсии. Я решил некоторые другие проблемы с помощью рекурсии, например, создал двоичное дерево, Ханойские башни и т. Д. Итак, я понимаю, что такое рекурсия, но у меня возникают трудности с планированием и реализацией правильного рекурсивного решения.

Существуют ли общие советы по планированию, обдумыванию или внедрению рекурсивных решений проблемы?

Answer 1

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

Поскольку факториал n! определяется как n * (n-1) * (n-2) ... * 1, вы должны увидеть, что

n! = n * (n-1)!

Другими словами, Факториал n равен «n раз факториала (n-1)» .

Если вы можете понять это утверждение и то, как оно проявляет «самоподобное» поведение, тогда вы хорошо подготовлены к решению рекурсии. Критическая вещь, когда программирование рекурсии - это определение момента остановки, а НЕ выполнение рекурсивного вызова. В случае факториала вы останавливаетесь, когда число, которое вы пытаетесь определить факториалом, равно 1. Результат просто определяется как 1, поэтому вы возвращаете это значение вместо того, чтобы возвращать значение рекурсивного вызова функции.

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

Answer 2

В основном, просто думать о двух вещах:

• Может ли проблема быть выражена в той же (или аналогичной) проблеме, но с "более легкими" параметрами?
• Есть ли четкая точка, где эта более простая проблема становится тривиальной?

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

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

Я говорю «может», потому что даже проблемы, которые проявляют эти свойства, не всегда хорошо подходят для рекурсии, например:

// Add two unsigned inetegers.
unsigned int add (unsigned int a, unsigned int b) {
    if (a == 0)
        return b;
    return add (a - 1, b + 1);
}

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

^(a) Вы можете задаться вопросом, почему существует разница между чем-то вроде add выше и GCD или факториальными вычислениями. Ответ обычно заключается в том, насколько быстро «пространство поиска» (список всех возможных результатов) уменьшается с каждым рекурсивным вызовом.

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

Функция add, однако, совсем не сокращает пространство поиска, поэтому она не подходит для рекурсии.

Факториал также не сокращает пространство поиска так быстро, поскольку он вычитает единицу из аргумента при каждом рекурсивном вызове (аналогично add).

Однако люди все еще используют его, возможно потому, что вам не хватит места для факториала long , прежде чем количество рекурсивных вызовов изменится (64-разрядное целое число без знака будет содержать только около 20 !).

Answer 3

После определения того, что проблема может быть решена рекурсивно, одна из самых важных вещей, которую нужно сделать, - это определить, что будет условие остановки вашего рекурсивного алгоритма. Тривиальным примером является вычисление факториала: вы знаете, что вам следует остановиться либо при достижении 0 или 1 (независимо от того, что вы выберете), поэтому это должно быть первым, что вы проверяете при входе в свою функцию, прежде чем позволить рекурсии продолжить, если вы в итоге переполнение стека исключение:

public static int factorial(int n)
{
    if (n == 1)//I'm done
        return 1;
    return n * factorial(n - 1); //continue with the recursion
}

Это мой рецепт рекурсии: что за условие остановки? Поставьте его в качестве первого утверждения после ввода вашей рекурсивной функции.

Answer 4

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

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

Для задач Ханойских башен довольно легко сделать так, чтобы перемещение башни размера N было в основном таким же, как перемещение башен N-1 и одного диска.Тем не менее, неясно, не зная уже решения, какой диск должен быть N + 1;либо сверху, либо снизу.Нам нужна дополнительная информация.

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

Перемещение башни размером 1 - это то же самое, что перемещение одного диска;нет причин возвращаться.Другими словами, перемещение башни нулевого размера - это то же самое, что вообще ничего не делать, и вы можете полностью это пропустить.

Наконец;Вы должны идентифицировать инварианты , которые определяет ваша проблема, чтобы определять способ, которым вы фактически выполняете работу.По сути, все сводится к тому, чтобы найти то, что должен делать ваш алгоритм, чтобы меньшие подзадачи действительно выглядели как большая проблема, а затем повторялись только в этих условиях.Ханойская башня состоит в том, что ни одному диску не разрешено располагаться поверх меньшего диска.Другими словами, вам не разрешается помещать башню на диск меньшего размера, чем нижний диск этой башни.Еще несколько рассуждений о проблеме приведут нас к выводу, что если мы разделим башню в некоторой точке посередине и переставим диски ниже раскола в какое-то произвольное, но действительное расположение, то башня над расколом может пойти сверхулюбого из этих переставленных дисков, так как каждый из них должен быть больше, чем диск на разделении.Аналогичный случай не может быть сделан для перестановки дисков над разъемом;на верхнем диске ничего не разрешается.

В целом это означает, что мы должны работать с снизу вверх ;разделительная башня на нижнем диске.Это также означает, что вырожденный случай, n = 1, перемещает верхний диск.Таким образом, рекурсивный алгоритм состоит в том, чтобы рекурсивно переместить диски N-1 в сторону, переместить n-й диск в место назначения, а затем переместить диски N-1 в место назначения., тогда вы можете задать более конкретный вопрос