Cara umum untuk mengubah loop (sementara / untuk) menjadi rekursi atau dari rekursi menjadi satu loop?

Masalah ini terutama berfokus pada algoritma, mungkin sesuatu yang abstrak dan lebih bersifat akademis.

Contohnya adalah menawarkan pemikiran, saya ingin cara yang umum, jadi contoh hanya digunakan untuk membuat kami lebih jelas tentang pemikiran Anda.

Secara umum, loop dapat dikonversi menjadi rekursif.

misalnya:

for(int i=1;i<=100;++i){sum+=i;}

Dan rekursif terkait adalah:

int GetTotal(int number)
{
   if (number==1) return 1;   //The end number
   return number+GetTotal(number-1); //The inner recursive
}

Dan akhirnya untuk menyederhanakan ini, rekursif ekor diperlukan:

int GetTotal (int number, int sum)
{
    if(number==1) return sum;
    return GetTotal(number-1,sum+number);
}

Namun, kebanyakan kasus tidak mudah dijawab dan dianalisis. Yang ingin saya ketahui adalah:

1) Bisakah kita mendapatkan "cara umum umum" untuk mengonversi loop (untuk / sementara ……) menjadi rekursif? Dan hal-hal apa yang harus kita perhatikan ketika melakukan pertobatan? Akan lebih baik untuk menulis info terperinci dengan beberapa sampel dan teori persudo Anda serta proses konversi.

2) "Rekursif" memiliki dua bentuk: Linely rekursif dan Ekor-Rekursif. Jadi mana yang lebih baik untuk dikonversi? "Aturan" apa yang harus kita kuasai?

3) Kadang-kadang kita perlu menjaga "sejarah" rekursif, ini mudah dilakukan dalam pernyataan loop:

misalnya:

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);
   }
}

Hasilnya di bawah ini adalah:

Hasil 1 adalah 1.

Hasil 1 + 2 adalah 3.

1 + 2 + 3 hasilnya 6 …………

Namun saya pikir sulit untuk menyimpan sejarah dalam rekursif, karena algoritma berbasis rekursif berfokus pada untuk mendapatkan hasil terakhir dan melakukan panggilan balik. Jadi semua ini dilakukan melalui stack yang dikelola oleh bahasa pemrograman yang menetapkan memori dalam bentuk stack secara otomatis. Dan bagaimana kita dapat "secara manual" mengeluarkan masing-masing "nilai tumpukan" dan mengembalikan beberapa nilai melalui algoritma rekursif?

Dan bagaimana dengan "dari algoritma rekursif ke loop"? Bisakah mereka dipertobatkan satu sama lain (saya pikir itu harus dilakukan secara teoritis, tetapi saya ingin hal-hal yang lebih akurat untuk membuktikan pikiran saya) .

Sebenarnya Anda harus memecah fungsi terlebih dahulu:

Loop memiliki beberapa bagian:

1. header, dan memproses sebelum loop. Dapat mendeklarasikan beberapa variabel baru

2. kondisi, kapan harus menghentikan loop.

3. tubuh loop yang sebenarnya. Ini mengubah beberapa variabel header dan / atau parameter yang dikirimkan.

4. ekor; apa yang terjadi setelah loop dan mengembalikan hasilnya.

Atau untuk menuliskannya:

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

Menggunakan blok ini untuk membuat panggilan rekursif cukup mudah:

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

Et voilà; versi rekursif ekor dari setiap loop. breaks dan continues dalam loop body masih harus diganti dengan return taildan kembali foo_recursion(params, modified_header_vars)sesuai kebutuhan tetapi itu cukup sederhana.

Melangkah ke arah lain lebih rumit; sebagian karena mungkin ada beberapa panggilan rekursif. Ini berarti bahwa setiap kali kita mengeluarkan bingkai tumpukan dapat ada banyak tempat di mana kita perlu melanjutkan. Juga mungkin ada variabel yang perlu kita simpan di seluruh panggilan rekursif dan parameter asli panggilan.

Kita dapat menggunakan sakelar untuk mengatasi itu:

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;
        }
    }
}

Menindaklanjuti jawaban @ratchet freak, saya membuat contoh ini tentang bagaimana fungsi Fibonacci dapat ditulis ulang ke loop sementara di Java. Perhatikan bahwa Ada cara yang jauh lebih sederhana (dan efisien) untuk menulis ulang Fibonacci dengan loop sementara.

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;
}