Problem ten koncentruje się głównie na algorytmie, być może czymś abstrakcyjnym i bardziej akademickim.
Przykład oferuje myśl, chcę ogólny sposób, więc przykład został użyty tylko w celu wyraźniejszego wyjaśnienia twoich myśli.
Ogólnie mówiąc, pętla może być przekształcona w rekurencyjną.
na przykład:
for(int i=1;i<=100;++i){sum+=i;}
Jego powiązanym rekurencyjnym jest:
int GetTotal(int number)
{
if (number==1) return 1; //The end number
return number+GetTotal(number-1); //The inner recursive
}
Wreszcie, aby to uprościć, potrzebny jest rekursywny ogon:
int GetTotal (int number, int sum)
{
if(number==1) return sum;
return GetTotal(number-1,sum+number);
}
Jednak większość przypadków nie jest tak łatwa do odpowiedzi i analizy. Chcę wiedzieć:
1) Czy możemy uzyskać „ogólny wspólny sposób” konwersji pętli (na / podczas ……) na rekurencyjną? Na jakie rzeczy powinniśmy zwracać uwagę podczas nawracania? Lepiej byłoby napisać szczegółowe informacje z niektórymi próbkami i teoriami persudo, a także z procesem konwersji.
2) „Recursive” ma dwie formy: Linely rekurencyjne i Tail-Recursive. Więc co lepiej przekonwertować? Jaką „zasadę” powinniśmy opanować?
3) Czasami musimy zachować „historię” rekurencji, można to łatwo zrobić za pomocą instrukcji pętli:
na przykład:
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);
}
}
Poniższy wynik to:
Wynik 1 to 1.
Wynik 1 + 2 to 3.
Wynik 1 + 2 + 3 to 6 …………
Myślę jednak, że trudno jest utrzymać historię w rekursywnym, ponieważ algorytm oparty na rekurencyjnych skupia się na uzyskaniu ostatniego wyniku i wykonaniu funkcji oddzwaniania. Wszystko to odbywa się poprzez stos obsługiwany przez język programowania, który automatycznie przypisuje pamięć w postaci stosu. I w jaki sposób możemy „ręcznie” wyjąć każdą z „wartości stosu” i zwrócić wiele wartości za pomocą algorytmu rekurencyjnego?
A co z „od algorytmu rekurencyjnego do pętli”? Czy można je nawzajem przekonać (myślę, że należy to zrobić teoretycznie, ale chcę, aby bardziej dokładne rzeczy potwierdziły moje myśli) .
źródło
Odpowiedzi:
Właściwie najpierw powinieneś rozbić tę funkcję:
Pętla składa się z kilku części:
nagłówek i przetwarzanie przed pętlą. Może zadeklarować nowe zmienne
warunek, kiedy zatrzymać pętlę.
rzeczywiste ciało pętli. Zmienia niektóre zmienne nagłówka i / lub przekazane parametry.
ogon; co dzieje się po pętli i zwraca wynik.
Lub napisać to:
Użycie tych bloków do wykonania rekurencyjnego połączenia jest dość proste:
Gotowe; rekurencyjna wersja dowolnej pętli.
break
sicontinue
w korpusie pętli będą nadal musiały zostać zastąpionereturn tail
ifoo_recursion(params, modified_header_vars)
w razie potrzeby powróciły , ale jest to dość proste.Idąc w drugą stronę jest bardziej skomplikowana; częściowo dlatego, że może istnieć wiele wywołań rekurencyjnych. Oznacza to, że za każdym razem, gdy otwieramy ramkę stosu, może istnieć wiele miejsc, w których musimy kontynuować. Mogą też istnieć zmienne, które musimy zapisać w wywołaniu rekurencyjnym i oryginalnych parametrach wywołania.
Możemy użyć przełącznika, aby obejść ten problem:
źródło
Idąc za odpowiedzią @ratchet freak, stworzyłem ten przykład, w jaki sposób funkcja Fibonacciego może zostać przepisana do pętli while w Javie. Zauważ, że istnieje znacznie prostszy (i skuteczny) sposób na przepisanie Fibonacciego za pomocą pętli while.
źródło