Блог

Главная - Вопросы по программированию - Перегрузка и рекурсия

Перегрузка и рекурсия

#recursion #overloading

#рекурсия #перегрузка

Вопрос:

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

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

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

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

Вот примерный пример:

 int fibonacci(int n) {
    if (n == 1)
        return 1;
    else
        return fibonacci(n, 2, 1, 2);
}

int fibonacci(int n, int f1, int f2, int c) {
    if (c == n)
        return f1;
    else
        return fibonacci(n, f1   f2, f1, c   1);
}

Это все еще рекурсия в смысле определения? Будет ли это работать? Будут ли компиляторы, выполняющие оптимизацию рекурсии (не знаю, как это точно работает, но знаю, что оно существует), применять это к этому?

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

Комментарии:

1. Кроме того, вы допустили ошибку, которая очень распространена среди людей, пишущих рекурсивные функции: вы забыли return значение вызова функции (например return fibonacci(...) ).

2. Просто исправил это, что странно, поскольку программа все еще выполнялась и выводила ответ, когда я выполнял cout << fibonacci(n)

3. да, это, вероятно, потому, что последний вызов функции возвращает f1 fibonacci(int, int, int, int) искомое число Фибоначчи (поэтому оно хранится в регистре eax, если вы используете x86), и return s должен продвигать это вверх, но они этого не делают, но поскольку return s нет, значение последнего вызова функции равноне перезаписывается, так что это просто работает. Но это не всегда будет работать на всех архитектурах, и это технически недопустимо C , потому что «не все пути возвращают значение», о котором ваш компилятор должен вас предупредить.

4. Это «стандартный» способ рекурсивной обработки Фибоначчи. Перегрузка не имеет значения, поскольку имена могут быть полностью случайными и при этом иметь желаемую семантику (даже если это будет считаться «плохим кодом») — в статически типизированном языке с перегрузкой сигнатура типа является частью «имени». Хотя функция «prep» сама по себе не является рекурсивной, вторая функция явно является — и именно в этой функции фактически выполняется работа.

5. Еще одно замечание: функция main / original / prep не обрабатывает базовый вариант. Базовый случай — это когда рекурсия заканчивается (в вашем примере (c==n) ) и обрабатывается вспомогательной функцией. Вы можете удалить тест для n==1 из основной функции и просто return fibonacci(n, 1, 1, 1) .

Ответ №1:

Да, я бы все равно назвал это «рекурсией». Перегрузка с одним аргументом fibonacci не является рекурсивной, но перегрузка с 4 аргументами, без сомнения, является рекурсивной.

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

Комментарии:

1. Я знаю, я просто всегда чувствую себя глупо, когда пишу многопараметрическую функцию и пишу: «Предположим, что эти переменные — это, это и то, а n — запрошенное число Фибоначчи».

2. @Portaljacker не забывайте об аргументах по умолчанию (если вы используете C ).

3. Подождите, что? Не знал об этом! Какой синтаксис? Я предполагаю, что вы можете заменить эти значения в последовательных рекурсивных вызовах, верно? Какие другие языки поддерживают это? Большая часть моих классных работ написана на Java, но некоторые — на C , так что полезно знать такие вещи!

4. @Portaljacker ваша сигнатура функции будет выглядеть fibonacci(int n, int f1 = 2, int f2 = 1, int c = 2) следующим образом . Таким образом, вы можете вызвать его с одним или несколькими (но менее 4) аргументами, а остальные будут иметь свои значения по умолчанию, или вы можете вызвать его со всеми из них, и они будут иметь эти значения.

5. Большое вам спасибо! Мне кажется, что я это где-то видел, но я никогда не был уверен, выдумал я это или нет. Есть идеи о других языках, которые это делают?