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

Question

Мне нравится решать проблемы алгоритмов на сайте TopCoder. Я могу реализовать большинство базовых рекурсивных проблем, таких как обратное отслеживание, dfs ... Однако, когда я сталкиваюсь со сложной рекурсией, это часто занимает у меня часы и часы. И когда я проверяю решение других программистов, мне так стыдно за себя. Я программирую почти 5 лет. Я вижу значительное улучшение в других методах программирования, таких как манипуляции со строками, графикой, GUI ... но не рекурсия? Может кто-нибудь поделиться опытом как подойти к рекурсивным проблемам? Спасибо!

Обновление

Я знаком с методикой юнит-теста. Еще до того, как я познакомился с модульным тестом, я часто писал небольшие тестовые функции, чтобы увидеть, какой результат мне нужен. Столкнувшись с рекурсивными проблемами, я потерял эту способность естественным образом. Я могу вставить несколько операторов «cout», чтобы увидеть текущий результат, но когда вызов глубоко вложен, я больше не могу его отслеживать. Поэтому большую часть времени я либо решал сначала с помощью карандаша и бумаги, либо готов (не могу использовать обычный метод, например, разбить его на более мелкие кусочки). Я чувствую, что рекурсия должна работать в целом.

С уважением,
Chan

Answer 1

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

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

Answer 2

Это очень хороший вопрос.

Лучший ответ, который у меня есть, - это факторинг: разделяй и властвуй. Это немного сложно в C ++, потому что он не поддерживает функции высшего порядка, но вы можете сделать это. Самые распространенные процедуры - это карты и сгибы. [C ++ уже имеет cofold, называемый std :: аккумулировать].

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

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

Другой способ сделать это (и я сожалею об этом) - это сначала использовать настоящий язык программирования, такой как Ocaml или Haskell, а затем попытаться перевести хороший чистый код на C ++. Таким образом, вы сможете легче увидеть структуру, не увязая в подробностях уборки, уродливом синтаксисе, отсутствии локализации и прочем. Если у вас все получилось, вы можете механически перевести его на C ++. (Или вы можете использовать Феликс, чтобы перевести его для вас)

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

let rec addup (ls: int list) : int = match ls with 
| [] -> 0                (* empty list *)
| h::t -> h + addup t    (* add head to addup of tail: TRUST addup to work *)

Это не хвостовая рекурсия, но это:

let addup (ls: int list) : int = 
  let rec helper ls sum = match ls with
  | [] -> sum
  | h :: t -> helper t (h+ sum)
  in
helper ls 0

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

Answer 3

Получите копию Маленький интриган и проработайте упражнения.

Не отвлекайтесь на книгу, используя Scheme вместо C ++ или C #или каков твой любимый язык. Дуглас Крокфорд говорит (о более раннем издании, называемом Маленький ЛИСПЕР ):

В 1974 году Даниэль П. Фридман опубликовал небольшую книгу под названием Маленький ЛИСПЕР .Это было всего 68 страниц, но оно сделало замечательную вещь: оно могло научить вас мыслить рекурсивно.В нем использовался какой-то притворный диалект LISP (который был написан всеми заглавными буквами в те дни).Диалект не полностью соответствовал какому-либо настоящему LISP.Но это было нормально, потому что речь шла не о LISP, а о рекурсивных функциях.

Answer 4

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

1) Определите свою проблему в слове своего владельца и сделайте несколько удачных примеров.

2) Сделайте наблюдения, рассмотрите крайние случаи, ограничения (например: «Алгоритм должен быть в худшем случае O (n log n)»)

3) Решите, как решить проблему: теория графов, динамическое программирование (отречение), комбанитромика.

Отсюда и далее рекурсия:

4) Определите «подзадачу», часто бывает полезно угадать, сколько подзадач может быть из ограничений, и использовать ее для угадывания. В конце концов подзадача «щелкнет» в вашей голове.

5) Выберите восходящий или нисходящий алгоритм.

6) Код!

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

Ходьба всегда помогает мне выработать алгоритм, может быть, он вам тоже поможет!

Answer 5

Какие части проблемы занимают у вас часы и часы?

А как насчет решения других кодеров, которое вы сами не поняли?

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

Answer 6

• Идентифицировать Base case: то есть это идентифицирует случай, когда прекратить рекурсивную обработку

  Ex: if (n == null) { return 0; }

• Определите sub-problem, разбив задачу на наименьший возможный случай.

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

• рекурсия головы
• хвостовая рекурсия

При head recursive подходе происходит рекурсивный вызов, а затем обработка. мы обрабатываем «остальную часть» списка перед обработкой первого узла. Это позволяет нам избежать передачи дополнительных данных в рекурсивном вызове.

При tail recursive подходе обработка происходит до рекурсивного вызова

Answer 7

попробуйте автоматическое запоминание в c ++ 0x :).Оригинальный пост: http://slackito.com/2011/03/17/automatic-memoization-in-cplusplus0x/

и мой мод для рекурсивных функций:

#include <iostream>
#include <functional>
#include <map>

#include <time.h>

//maahcros
#define TIME(__x) init=clock(); __x; final=clock()-init; std::cout << "time:"<<(double)final / ((double)CLOCKS_PER_SEC)<<std::endl;
#define TIME_INIT  clock_t init, final;
void sleep(unsigned int mseconds) { clock_t goal = mseconds + clock(); while (goal > clock()); }

//the original memoize
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end()) {
            cache[t] = func(args...);
        }
        return cache[t];
    });
}

/// wrapped factorial
struct factorial_class {

    /// the original factorial renamed into _factorial
    int _factorial(int n) {
        if (n==0) return 1;
        else {
         std::cout<<" calculating factorial("<<n<<"-1)*"<<n<<std::endl;
         sleep(100);
         return factorial(n-1)*n;
        }
    }

    /// the trick function :)
    int factorial(int n) {
        if (memo) return (*memo)(n);
        return _factorial(n);
    }

    /// we're not a function, but a function object
    int operator()(int n) {
        return _factorial(n);
    }

    /// the trick holder
    std::function<int(int)>* memo;

    factorial_class() { memo=0; }
};

int main()
{
 TIME_INIT
    auto fact=factorial_class(); //virgin wrapper
    auto factorial = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy
    fact.memo=&factorial; //spoilt wrapper
    factorial = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy

    TIME ( std::cout<<"factorial(3)="<<factorial(3)<<std::endl; ) // 3 calculations
    TIME ( std::cout<<"factorial(4)="<<factorial(4)<<std::endl; ) // 1 calculation
    TIME ( std::cout<<"factorial(6)="<<factorial(6)<<std::endl; ) // 2 calculations
    TIME ( std::cout<<"factorial(5)="<<factorial(5)<<std::endl; ) // 0 calculations

    TIME ( std::cout<<"factorial(12)="<<factorial(12)<<std::endl; )
    TIME ( std::cout<<"factorial(8)="<<factorial(8)<<std::endl;  )
    return 0;
}

Answer 8

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

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

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

Answer 9

Динамическое программирование помогает.Памятка также полезна.