При написании программы рекурсии последовательности Recamans, почему счетчик продолжает двигаться вверх и вниз?
Я пытаюсь изучить рекурсию. Я пытался написать последовательность Recamans с помощью рекурсивной функции.
#include <stdio.h>
int recursion(int inputnum){
if (inputnum==0){
printf("term %d, zero returned\n",inputnum);
return 0;
}
else {
if ((recursion(inputnum-1)-inputnum)<0){
printf("returning %d at term %d \n",(recursion(inputnum-1)+ inputnum),inputnum);
return (recursion(inputnum-1)+inputnum);
}
else {
printf("returning %d at term %d \n",(recursion(inputnum-1)- inputnum),inputnum);
return (recursion(inputnum-1)-inputnum);
}
}
}
int main(void){
int numberofterms;
numberofterms=3;
printf("%d",recursion(numberofterms));
}
Насколько я знаю, мне нужно установить базовый вариант для функции, которая будет возвращать простейшее значение для задачи, и в случае моей программы переменная inputnum должна увеличиваться после того, как она достигнет 0. Однако Оператор отладки, который я поставил {printf("term %d, zero returned\n",inputnum);}, все еще продолжает появляться после того, как значение inputnum, похоже, увеличилось. Кто-нибудь любезно укажет на проблемы в этой программе?
Первый оператор отладки не выглядит особенно интересным, просто говорит, что возвращается 0. Ваш второй оператор отладки неверен, поскольку у вас есть два разных вызова, но вы печатаете только первое ожидаемое значение.
Я допустил там ошибку. Однако я хотел спросить, что после того, как inputnum станет 0, должна быть возвращена рекурсия (0) -> рекурсия (1)...? Потому что, когда я запускаю код, оператор отладки в условии (когда inputnum==0) продолжает появляться, что заставляет меня задуматься, что происходит во время этого процесса.
Ответы 1
Последовательность Рекамана действительно идет вверх и вниз. Вывод вашей отладки не только изначально неправильный, но и сбивает вас с толку, потому что у вас есть 3 рекурсивных вызова для inputnum > 0. Вместо этого вы хотите один раз вычислить recursive(inputnum-1) и присвоить его временной переменной.
#include <stdio.h>
#define N 6
int recursion(int n) {
if (n == 0) return 0;
int tmp = recursion(n-1);
if (tmp - n > 0) return tmp - n; // TODO: "and not already in the sequence"
return tmp + n;
}
int main() {
for(int i = 0; i < N; i++)
printf("%d%s", recursion(i), i + 1 < N ? ", " : "\n");
}
и вот пример вывода:
0, 1, 3, 6, 2, 7
Следующим шагом будет использование динамического программирования (DP) для сохранения последовательности в массиве, чтобы вы могли использовать эти частичные результаты вместо того, чтобы снова и снова вычислять одно и то же. Это также позволит вам решить задачу TODO, указанную выше.
Написание if (tmp - n > 0) — забавный способ письма if (tmp > n).
@JonathanLeffler В конце концов я решил, что для ОП будет наиболее полезно увидеть прямой перевод алгоритма, найденный в Википедии. Я предпочитаю последнее. Я нашел некоторое утешение, увидев, что термин tmp - n встречается дважды.
Теперь вы должны рассказать нам, как вы рассчитываете последовательность Рекамана. Предполагается ли, что базовый вариант reduction(0) равен 0? Какое значение ожидается для входа 1? и т. д. Результатом является одно число, поэтому я понимаю, как оно связано с последовательностью.