Когда использовать рекурсию?

Когда есть некоторые (относительно) базовые (например, первокурсник, студент CS-уровня), когда можно использовать рекурсию, а не просто цикл?

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

Я думаю, что Дейв хорошо резюмирует это: используйте это там, где это уместно. То есть используйте его, когда он кажется естественным. Когда вы сталкиваетесь с проблемой, когда она хорошо подходит, вы, скорее всего, узнаете ее: может показаться, что вы даже не можете найти итеративное решение. Кроме того, ясность является важным аспектом программирования. Другие люди (и вы тоже!) Должны иметь возможность читать и понимать код, который вы создаете. Я думаю, можно с уверенностью сказать, что итерационные циклы легче понять с первого взгляда, чем рекурсию.

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

Содержит ли строка символ ?$x$

Вот как мы делали это раньше: перебираем строку и проверяем, содержит ли индекс .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

Вопрос в том, можем ли мы сделать это рекурсивно? Конечно, мы можем, вот один из способов:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

Тогда возникает следующий естественный вопрос: должны ли мы сделать это так? Возможно нет. Зачем? Это сложнее понять и сложнее придумать. Следовательно, он также более подвержен ошибкам.

Решения некоторых проблем более естественно выражаются с помощью рекурсии.

Например, предположим, что у вас есть древовидная структура данных с двумя типами узлов: листья, которые хранят целочисленное значение; и ветви, которые имеют левое и правое поддерево в своих полях. Предположим, что листья упорядочены, так что самое низкое значение находится в крайнем левом листе.

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

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Написание эквивалентного кода без рекурсии было бы намного сложнее. Попытайся!

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

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

Также обратите внимание, что функциональные языки программирования выполняют оптимизированную хвостовую рекурсию. Это означает, что они не устанавливают фрейм стека, если они не нуждаются - по существу, рекурсия может быть преобразована в цикл. С практической точки зрения вы можете писать код естественным образом, но получить производительность итеративного кода. Напомним, что компиляторы C ++ также оптимизируют хвостовые вызовы , поэтому нет никаких дополнительных затрат на использование рекурсии в C ++.

От того, кто практически живет в рекурсии, я постараюсь пролить свет на эту тему.

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

Если вы узнаете больше о функциональном программировании, таком как F #, вы узнаете, что списки F # реализованы в виде односвязных списков, что означает, что операции, которые обращаются только к заголовку списка, являются O (1), а доступ к элементу - O (n). Когда вы узнаете это, вы стремитесь просмотреть данные в виде списка, создавая новый список в обратном порядке, а затем переворачивая список, прежде чем вернуться из функции, которая очень эффективна.

Теперь, если вы начнете думать об этом, вы скоро поймете, что рекурсивные функции будут выдвигать кадр стека каждый раз, когда выполняется вызов функции, и могут вызвать переполнение стека. Однако, если вы создаете свою рекурсивную функцию, чтобы она могла выполнять хвостовой вызов, а компилятор поддерживает возможность оптимизировать код для хвостового вызова. т.е. .NET OpCodes.Tailcall Field вы не будете вызывать переполнение стека. С этого момента вы начинаете писать любой цикл как рекурсивную функцию, а любое решение - как совпадение; дни ifи whileтеперь история.

Как только вы переходите на ИИ, используя возврат на таких языках, как PROLOG, все становится рекурсивным. Хотя для этого нужно думать совершенно иначе, чем просто для императивного кода, если PROLOG является подходящим инструментом для решения проблемы, он освобождает вас от необходимости писать много строк кода и может значительно сократить количество ошибок. Смотрите: Amzi клиент eoTek

Вернемся к вашему вопросу о том, когда использовать рекурсию; Я смотрю на программирование одним способом: на одном конце - аппаратное обеспечение, а на другом - абстрактные концепции. Чем ближе к проблеме аппаратного обеспечения, тем больше я думаю о императивных языках ifи whileчем более абстрактно эта проблема, тем больше я думаю о языках высокого уровня с рекурсией. Однако, если вы начнете писать системный код низкого уровня и тому подобное и хотите убедиться, что он действителен, вам пригодятся такие решения, как средства доказательства теорем , которые в значительной степени зависят от рекурсии.

Если вы посмотрите на улицу Джейн, вы увидите, что они используют функциональный язык OCaml . Хотя я не видел ни одного из их кода, прочитав о том, что они упоминают о своем коде, они угрюмо думают рекурсивно.

РЕДАКТИРОВАТЬ

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

Для C ++: если вы определяете структуру или класс, который имеет указатель на ту же структуру или класс, тогда рекурсия должна быть рассмотрена для методов обхода, которые используют указатели.

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

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

Обычное использование рекурсии:

• сортировка
• поиск
• карта
• складка
• фильтр

Чтобы дать вам вариант использования, который является менее загадочным, чем те, которые приведены в других ответах: рекурсия очень хорошо сочетается со структурами древовидных (объектно-ориентированных) классов, происходящими из общего источника. Пример C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

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

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

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

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Или что-то в этом роде (я ухожу по памяти, а не тестирую). Кроме того, когда вы попадете в классы более высокого уровня, вы будете использовать рекурсию LOT, особенно в алгоритмах поиска, алгоритмах сортировки и т. Д.

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