Эта проблема в основном сосредоточена на алгоритме, может быть, что-то абстрактное и более академическое.
Пример предлагает мысль, я хочу общий способ, поэтому пример используется только для того, чтобы сделать нас более ясно о ваших мыслях.
Вообще говоря, цикл может быть преобразован в рекурсивный.
например:
for(int i=1;i<=100;++i){sum+=i;}
И связанный с ним рекурсив:
int GetTotal(int number)
{
if (number==1) return 1; //The end number
return number+GetTotal(number-1); //The inner recursive
}
И, наконец, чтобы упростить это, нужна хвостовая рекурсия:
int GetTotal (int number, int sum)
{
if(number==1) return sum;
return GetTotal(number-1,sum+number);
}
Тем не менее, в большинстве случаев не так просто ответить и проанализировать. То, что я хочу знать, это:
1) Можем ли мы получить «общий общий способ» преобразования цикла (для / в то время как ……) в рекурсивный? И на какие вещи мы должны обращать внимание при обращении? Было бы лучше написать подробную информацию с некоторыми образцами и вашими теориями персудо, а также процессом конверсии.
2) «Рекурсивный» имеет две формы: линейно-рекурсивный и хвост-рекурсивный. Так что лучше конвертировать? Какое «правило» мы должны освоить?
3) Иногда нам нужно сохранить рекурсивную «историю», это легко сделать в операторе цикла:
например:
List<string> history = new List<string>();
int sum=0;
for (int i=1;i<=100;++i)
{
if(i==1) history.Add(i.ToString()+"'s result is:1.");
else
{
StringBuilder sub = new StringBuilder();
for(int j=1;j<=i;++j)
{
if(j==i) sbu.Append(j.ToString());
else
{
sub.Append(j.ToString()+"+");
}
}
sum +=i;
sbu.Append("'s result is:"+sum+Environment.NewLine);
}
}
Результат ниже:
1 результат 1.
1 + 2 результат 3.
Результат 1 + 2 + 3 - 6 …………
Однако я думаю, что трудно сохранять историю в рекурсивном режиме, потому что алгоритм на основе рекурсии фокусируется на получении последнего результата и выполнении обратного вызова. Таким образом, все это выполняется через стек, поддерживаемый языком программирования, который автоматически выделяет память в виде стека. И как мы можем «вручную» извлечь каждое из «значений стека» и вернуть несколько значений через рекурсивный алгоритм?
А как насчет "от рекурсивного алгоритма до цикла"? Могут ли они быть обращены друг к другу (я думаю, что это должно быть сделано теоретически, но я хочу более точные вещи, чтобы доказать свои мысли) .
источник
Ответы:
На самом деле вы должны сначала сломать функцию:
Цикл состоит из нескольких частей:
заголовок и обработка перед циклом. Может объявить некоторые новые переменные
условие, когда остановить цикл.
фактическое тело цикла. Он изменяет некоторые переменные заголовка и / или передаваемые параметры.
хвост; что происходит после цикла и возврата результата.
Или написать это:
Использование этих блоков для создания рекурсивного вызова довольно просто:
И вуаля; хвостовая рекурсивная версия любого цикла.
break
s иcontinue
s в теле цикла все равно придется заменятьreturn tail
и возвращать поfoo_recursion(params, modified_header_vars)
мере необходимости, но это достаточно просто.Идти другим путем сложнее; отчасти потому, что может быть несколько рекурсивных вызовов. Это означает, что каждый раз, когда мы извлекаем кадр стека, может быть несколько мест, где нам нужно продолжить. Также могут быть переменные, которые нам нужно сохранить в рекурсивном вызове и исходные параметры вызова.
Мы можем использовать переключатель, чтобы обойти это:
источник
Следуя ответу @ratchet freak, я создал этот пример того, как функция Фибоначчи может быть переписана в цикл while в Java. Обратите внимание, что существует гораздо более простой (и эффективный) способ переписать Фибоначчи с помощью цикла while.
источник