Рекурсия + возврат. Что вернуть?

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

Например, если ответ должен быть ArrayList, я не могу вернуть false, чтобы сказать, что это не работает. - Должен ли я возвращать дозорное значение, такое как null или -1, и проверять его в рекурсивном вызове? - Или функция должна просто возвращать void, и я добавляю переменную вне функции только в том случае, если я решу, что есть ответ - Или я должен сохранить дополнительный параметр, который содержит значение, и просто игнорировать его, если он не работает (я я не уверен, как это сделать в моем текущем примере) - Или я должен сначала иметь функцию, которая проверяет, работает ли она, а затем выполняет действие

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


string recursion algorithm backtracking
person user1136342    schedule 14.02.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

person Oleg Vaskevich    schedule 14.02.2013

arrow_upward
0
arrow_downward

Из вашего вопроса я предполагаю, что у вас есть что-то, что действует следующим образом:

struct my_object *rec_foo(int param /* ... */)
{
    my_object *tmp = NULL;
    int x;
    /*
     * Do something
     */

    /*
     * Here you don't know how to handle
     * the case where rec_foo() fails
     */
    tmp = rec_foo(x /* ... */);
    /*
     * Other work
     */
    return tmp;
}

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

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

enum rec_foo_error {
    REC_FOO_NO_ERROR,
    REC_FOO_ERROR_1,
    REF_FOO_ERROR_LAST /* Just to retrieve quickly
                      the number of available errors */
};
// You could simply use an int instead, but this is elegant
enum rec_foo_error rec_foo(struct my_object *obj, int x /*, ... */);
person Rerito    schedule 14.02.2013