Как написать функцию цикла как рекурсивную функцию?

Ну, я пытался переделать это много раз. Хотя в какой-то момент я подумал, что функция longestSequence поможет, так как она отображает самую длинную последовательность градин. Хотя я не могу понять, как найти или сохранить значение, которое использовалось для поиска. Если бы кто-нибудь мог объяснить, как это сделать, я был бы признателен.

int longestSequence(int n)
{
    int u = n;

    if(u == 1)
    {
        return 1;
    }
    else 
    {
        return max(hailstoneLength(u), longestSequence(u-1));
    }
}

Часть, с которой у меня возникли проблемы, - это моя самая длинная последовательность запуска:

int hailLongestSeq(int n)
{
    int k;
    int longest = 0;
    for(int j = 1; j <= n; j++)
    {
        if(hailstoneLength(j) > longest)
        {
            longest = hailstoneLength(j);
            k = j;
        }
    }
    return k;   
}

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

Ожидаемый результат выглядит следующим образом:

Самая длинная последовательность градин, начинающаяся с числа до 10, имеет длину 20. Самая длинная последовательность градин, начинающаяся с числа до 10, начинается с 9.

поскольку последовательность 9 имеет длину 20 цифр и является самой длинной от 1 до 10.


c++ recursion
person Zabe    schedule 23.09.2016    source источник
comment
Разве ты не спрашивал об этом вчера?   -  person Ami Tavory    schedule 23.09.2016
comment
формула переформулирует проблему с точки зрения подзадач: пример: цикл for из n итераций — это итерация по циклу for из n-1 итераций   -  person perreal    schedule 23.09.2016
comment
Нет, я не спрашивал об этом вчера. Я представил это в час ночи сегодня   -  person Zabe    schedule 23.09.2016

Ответы (2)


arrow_upward
4
arrow_downward

Да, каждый цикл for может быть переведен в рекурсивный вызов, очевидно, так:

for (i=0; i<N; i++) {
  body;
}

перевести его на:

func(int i) {
  if (i<N) { body; func(i+1) }
  else return;
}

func(0);

Это может быть легко расширено для любого вычисления цикла for (добавьте параметры, если необходимо, возвращаемое значение и т. д.).

person Jean-Baptiste Yunès    schedule 23.09.2016
comment
Ух ты. Спасибо! Я все еще изучаю С++. Я, вероятно, должен сохранить это на случай, если мне это снова понадобится. - person Zabe; 23.09.2016
comment
Когда я делаю это, я получаю ошибку сегментации. Как это исправить? или я делаю что-нибудь не так? - person Zabe; 23.09.2016

arrow_upward
0
arrow_downward

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

int hailLongestSeq(int n, int j, int k, int longest)
{
    if(j <= n)
    {
        if(hailstoneLength(j) > longest)
        {
            longest = hailstoneLength(j);
            k = j;
        }
        k = hailLongestSeq(n, ++j, k, longest);
    }
    return k;   
}

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

person Rishabh Kumar    schedule 23.09.2016
comment
То же самое с этим, у меня ошибка сегментации - person Zabe; 23.09.2016
comment
Извините, я случайно добавил j++ вместо ++j, что привело к бесконечному циклу. Я изменил код сейчас. Можете ли вы проверить еще раз и подтвердить, работает ли он для вас. - person Rishabh Kumar; 23.09.2016
comment
О да, это работает, Ришаб, спасибо. Спасибо, и если все в порядке, ничего, если я могу получить объяснение того, как это работает? Я работаю над большим количеством ручных симуляций. - person Zabe; 24.09.2016
comment
Ну, честно говоря, я только что преобразовал вашу логику цикла в рекурсию. Первое, что нужно преобразовать цикл, — это создать условие, основанное на вашем условии цикла. Если условие выполнено, снова вызовите функцию, иначе верните вывод. Также убедитесь, что все локальные переменные, используемые в функции, передаются в качестве параметров при выполнении рекурсивного вызова. Для сложных задач я всегда считаю, что лучше сначала написать циклы, а затем преобразовать их в рекурсивные функции. Продолжайте практиковаться. Пожалуйста, проголосуйте, если вы поняли. - person Rishabh Kumar; 24.09.2016
comment
Теперь я это хорошо понимаю, хотя, извините, я не могу проголосовать, так как у меня нет 15 представителей, но я заметил, что это также было объяснено выше. Когда я пошел по их пути, это привело к тому же. Спасибо еще раз. - person Zabe; 24.09.2016