Ogólny sposób konwersji pętli (while / for) na rekurencję lub z rekurencji na pętlę?

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) .

Właściwie najpierw powinieneś rozbić tę funkcję:

Pętla składa się z kilku części:

1. nagłówek i przetwarzanie przed pętlą. Może zadeklarować nowe zmienne

2. warunek, kiedy zatrzymać pętlę.

3. rzeczywiste ciało pętli. Zmienia niektóre zmienne nagłówka i / lub przekazane parametry.

4. ogon; co dzieje się po pętli i zwraca wynik.

Lub napisać to:

foo_iterative(params){
    header
    while(condition){
        loop_body
    }
    return tail
}

Użycie tych bloków do wykonania rekurencyjnego połączenia jest dość proste:

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Gotowe; rekurencyjna wersja dowolnej pętli. breaksi continuew korpusie pętli będą nadal musiały zostać zastąpione return taili foo_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:

bar_recurse(params){
    if(baseCase){
        finalize
        return
    }
    body1
    bar_recurse(mod_params)
    body2
    bar_recurse(mod_params)
    body3
}


bar_iterative(params){
    stack.push({init, params})

    while(!stack.empty){
        stackFrame = stack.pop()

        switch(stackFrame.resumPoint){
        case init:
            if(baseCase){
                finalize
                break;
            }
            body1
            stack.push({resum1, params, variables})
            stack.push({init, modified_params})
            break;
        case resum1:
            body2
            stack.push({resum2, params, variables})
            stack.push({init, modified_params})
            break;
        case resum2:
            body3
            break;
        }
    }
}

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.

class CallContext { //this class is similar to the stack frame

    Object[] args;

    List<Object> vars = new LinkedList<>();

    int resumePoint = 0;

    public CallContext(Object[] args) {
        this.args = args;
    }

}


static int fibonacci(int fibNumber) {
    Deque<CallContext> callStack = new LinkedList<>();
    callStack.add(new CallContext(new Object[]{fibNumber}));
    Object lastReturn = null; //value of last object returned (when stack frame was dropped)
    while (!callStack.isEmpty()) {
        CallContext callContext = callStack.peekLast();
        Object[] args = callContext.args;
        //actual logic starts here
        int arg = (int) args[0];
        if (arg == 0 || arg == 1) {
            lastReturn = arg;
            callStack.removeLast();
        } else {
            switch (callContext.resumePoint) {
                case 0: //calculate fib(n-1)
                    callStack.add(new CallContext(new Object[]{arg - 1}));
                    callContext.resumePoint++;
                    break;
                case 1: //calculate fib(n-2)
                    callContext.vars.add(lastReturn); //fib1
                    callStack.add(new CallContext(new Object[]{arg - 2}));
                    callContext.resumePoint++;
                    break;
                case 2: // fib(n-1) + fib(n-2)
                    callContext.vars.add(lastReturn); //fib2
                    lastReturn = (int) callContext.vars.get(0) + (int) callContext.vars.get(1);
                    callStack.removeLast();
                    break;
            }
        }
    }
    return (int) lastReturn;
}