Metode apa yang ada untuk menghindari stack overflow dalam algoritma rekursif?

Pertanyaan

Apa cara yang mungkin untuk menyelesaikan stack overflow yang disebabkan oleh algoritma rekursif?

Contoh

Saya mencoba menyelesaikan masalah Project Euler 14 dan memutuskan untuk mencobanya dengan algoritma rekursif. Namun, program berhenti dengan java.lang.StackOverflowError. Maklum. Algoritma memang meluap tumpukan karena saya mencoba untuk menghasilkan urutan Collatz untuk jumlah yang sangat besar.

Solusi

Jadi saya bertanya-tanya: apa cara standar yang ada untuk menyelesaikan stack overflow dengan asumsi algoritma rekursif Anda ditulis dengan benar dan akan selalu berakhir meluap stack? Dua konsep yang muncul di pikiran adalah:

1. rekursi ekor
2. perulangan

Apakah ide (1) dan (2) benar? Apakah ada opsi lain?

Sunting

Akan membantu untuk melihat beberapa kode, lebih disukai di Java, C #, Groovy atau Scala.

Mungkin tidak menggunakan masalah Project Euler yang disebutkan di atas sehingga tidak akan rusak bagi orang lain, tetapi ambil beberapa algoritma lainnya. Faktorial mungkin, atau yang serupa.

Optimasi panggilan ekor hadir dalam banyak bahasa dan kompiler. Dalam situasi ini, kompiler mengenali fungsi dari form:

int foo(n) {
  ...
  return bar(n);
}

Di sini, bahasa dapat mengenali bahwa hasil yang dikembalikan adalah hasil dari fungsi lain dan mengubah panggilan fungsi dengan bingkai tumpukan baru menjadi lompatan.

Sadarilah bahwa metode faktorial klasik:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

adalah tidak ekor panggilan optimizatable karena pemeriksaan yang diperlukan pada kembali. ( Contoh kode sumber dan hasil kompilasi )

Untuk membuat panggilan ekor ini dapat dioptimalkan,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Mengkompilasi kode ini dengan gcc -O2 -S fact.c(-O2 diperlukan untuk mengaktifkan pengoptimalan dalam kompiler, tetapi dengan lebih banyak optimasi dari -O3 semakin sulit bagi manusia untuk membaca ...)

_fact(int, int):
    cmpl    $1, %edi
    movl    %esi, %eax
    je  .L2
.L3:
    imull   %edi, %eax
    subl    $1, %edi
    cmpl    $1, %edi
    jne .L3
.L2:
    rep ret

( Contoh kode sumber dan hasil kompilasi )

Satu dapat melihat di segmen .L3, jnedaripada call(yang melakukan panggilan subrutin dengan bingkai tumpukan baru).

Harap dicatat ini dilakukan dengan C. Optimasi panggilan ekor di Jawa sulit dan tergantung pada implementasi JVM (yang mengatakan, saya belum melihat ada yang melakukannya, karena sulit dan implikasi dari model keamanan Java yang diperlukan yang memerlukan stack frames - yang harus dihindari TCO) - pengulangan-ekor + java dan pengulangan-ekor + optimisasi adalah kumpulan tag yang baik untuk dijelajahi. Anda mungkin menemukan bahasa JVM lain dapat mengoptimalkan rekursi ekor lebih baik (coba clojure (yang memerlukan pengulangan untuk mengoptimalkan panggilan pemanggilan), atau scala).

Yang mengatakan,

Ada kegembiraan tertentu karena mengetahui bahwa Anda menulis sesuatu dengan benar - dengan cara ideal yang bisa dilakukan.
_{^{Dan sekarang, saya akan mengambil scotch dan memakai electronica Jerman ...}}

Untuk pertanyaan umum "metode untuk menghindari tumpahnya tumpukan dalam algoritma rekursif" ...

Pendekatan lain adalah memasukkan counter rekursi. Ini lebih untuk mendeteksi loop tak terbatas yang disebabkan oleh situasi di luar kendali seseorang (dan kode yang buruk).

Counter rekursi mengambil bentuk

int foo(arg, counter) {
  if(counter > RECURSION_MAX) { return -1; }
  ...
  return foo(arg, counter + 1);
}

Setiap kali Anda melakukan panggilan, Anda menambah penghitung. Jika penghitung terlalu besar, Anda salah (di sini, hanya pengembalian -1, meskipun dalam bahasa lain Anda mungkin lebih suka membuang pengecualian). Idenya adalah untuk mencegah hal-hal buruk terjadi (kehabisan memori kesalahan) ketika melakukan rekursi yang jauh lebih dalam dari yang diharapkan dan kemungkinan loop tak terbatas.

Secara teori, Anda tidak perlu ini. Dalam praktiknya, saya telah melihat kode yang ditulis dengan buruk yang mengenai hal ini karena sejumlah besar kesalahan kecil dan praktik pengkodean yang buruk (masalah konkurensi multithreaded di mana sesuatu mengubah sesuatu di luar metode yang membuat utas lain masuk ke loop tak terbatas dari panggilan rekursif).

Gunakan algoritma yang tepat dan pecahkan masalah yang tepat. Khusus untuk dugaan Collatz, tampaknya Anda mencoba menyelesaikannya dengan cara xkcd :

Anda mulai dari angka dan melakukan traversal pohon. Ini dengan cepat mengarah ke ruang pencarian yang sangat besar. Jalankan cepat untuk menghitung jumlah iterasi untuk hasil jawaban yang benar dalam sekitar 500 langkah. Ini seharusnya tidak menjadi masalah untuk rekursi dengan bingkai tumpukan kecil.

Walaupun mengetahui solusi rekursif bukanlah hal yang buruk, kita juga harus menyadari bahwa berkali-kali solusi berulang lebih baik . Sejumlah cara mendekati konversi algoritma rekursif ke yang berulang dapat dilihat pada Stack Overflow di Way untuk beralih dari rekursi ke iterasi .

Perlu diingat bahwa implementasi bahasa harus mendukung optimasi rekursi ekor. Saya tidak berpikir kompiler java utama lakukan.

Memoisasi berarti Anda mengingat hasil perhitungan daripada menghitung ulang setiap waktu, seperti:

collatz(i):
    if i in memoized:
        return memoized[i]

    if i == 1:
        memoized[i] = 1
    else if odd(i):
        memoized[i] = 1 + collatz(3*i + 1)
    else
        memoized[i] = 1 + collatz(i / 2)

    return memoized[i]

Saat Anda menghitung setiap urutan kurang dari satu juta, akan ada banyak pengulangan di akhir urutan. Memoisasi menjadikannya pencarian tabel hash cepat untuk nilai-nilai sebelumnya daripada harus membuat tumpukan lebih dalam dan lebih dalam.

Saya terkejut bahwa belum ada yang menyebutkan trampolining . Trampolin (dalam pengertian ini) adalah sebuah loop yang secara iteratif memanggil fungsi-fungsi pemulangan kembali (gaya passing berkelanjutan) dan dapat digunakan untuk mengimplementasikan panggilan fungsi rekursif ekor dalam bahasa pemrograman stack-oriented.

Pertanyaan StackOverflow ini masuk ke sedikit lebih detail tentang berbagai implementasi trampolining di Jawa: Menangani StackOverflow di Java untuk Trampoline

Jika Anda menggunakan bahasa dan kompiler yang mengenali fungsi rekursif ekor dan menanganinya dengan benar (yaitu "mengganti penelepon dengan callee"), maka ya, tumpukan tidak boleh tumbuh di luar kendali. Optimalisasi ini pada dasarnya mengurangi metode rekursif menjadi metode berulang. Saya tidak berpikir Java melakukan ini, tetapi saya tahu bahwa Racket melakukannya.

Jika Anda menggunakan pendekatan berulang, bukan pendekatan rekursif, Anda menghilangkan banyak kebutuhan untuk mengingat dari mana panggilan berasal, dan secara praktis menghilangkan kemungkinan stack overflow (dari panggilan rekursif pula).

Memoisasi sangat bagus dan dapat mengurangi jumlah keseluruhan panggilan metode dengan mencari hasil yang sebelumnya dihitung dalam cache, mengingat bahwa perhitungan keseluruhan Anda akan dikenakan banyak perhitungan yang lebih kecil dan berulang. Gagasan ini hebat - itu juga terlepas dari apakah Anda menggunakan pendekatan berulang atau rekursif.

Anda dapat membuat Enumerasi yang akan menggantikan rekursi ... di sini adalah contoh untuk menghitung fakultas melakukan itu ... (tidak akan bekerja untuk angka besar karena saya hanya menggunakan panjang dalam contoh :-))

public class Faculty
{

    public static IEnumerable<long> Faculties(long n)
    {
        long stopat = n;

        long x = 1;
        long result = 1;

        while (x <= n)
        {
            result = result * x;
            yield return result;
            x++;
        }
    }
}

bahkan jika ini bukan memoisasi, dengan cara ini Anda akan membatalkan stack overflow

SUNTING

Saya minta maaf jika saya mengecewakan beberapa dari Anda. Satu-satunya niat saya adalah untuk menunjukkan cara bagaimana menghindari stack overflow. Saya mungkin harus menulis contoh kode lengkap alih-alih hanya sepotong kecil kutipan kode yang ditulis dengan cepat dan kasar.

Kode berikut

• menghindari rekursi karena saya menggunakan hitung nilai-nilai yang diperlukan secara iteratif.
• termasuk memoisasi karena Nilai yang sudah dihitung disimpan dan diambil jika sudah dihitung
• juga termasuk stopwatch, sehingga Anda dapat melihat bahwa memoisasi berfungsi dengan baik

... umm ... jika Anda menjalankannya pastikan Anda mengatur jendela shell perintah Anda untuk memiliki buffer 9999 baris ... 300 yang biasa tidak akan cukup untuk menjalankan melalui hasil dari program di bawah ini ...

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch w = new Stopwatch();
        static Faculty f = Faculty.GetInstance();

        static void Main(string[] args)
        {
            Out(5);
            Out(10);
            Out(-5);
            Out(0);
            Out(1);
            Out(4);
            Out(29);
            Out(30);
            Out(20);
            Out(10000);
            Out(20000);
            Out(19999);
            Console.ReadKey();
        }

        static void Out(BigInteger n)
        {
             try
            {
                w.Reset();
                w.Start();
                var x = f.Calculate(n);
                w.Stop();
                var time = w.ElapsedMilliseconds;
                Console.WriteLine(String.Format("{0} ({2}ms): {1}", n, x, time));
            }
            catch (ArgumentException e)
            {
                Console.WriteLine(e.Message);
            }

            Console.WriteLine("\n\n");
       }
    }

Saya menyatakan * 1 variabel statis "instance" di kelas Fakultas ke toko tunggal. Dengan cara itu selama program Anda berjalan, setiap kali Anda "GetInstance ()" dari kelas Anda mendapatkan instance yang telah menyimpan semua nilai yang sudah dihitung. * 1 SortedList statis yang akan menampung semua nilai yang sudah dihitung

Dalam konstruktor saya juga menambahkan 2 nilai khusus dari daftar 1 untuk input 0 dan 1.

    public class Faculty
    {
        private static SortedList<BigInteger, BigInteger> _values; 
        private static Faculty _faculty {get; set;}

        private Faculty ()
        {
            _values = new SortedList<BigInteger, BigInteger>();
            _values.Add(0, 1);
            _values.Add(1, 1);
        }

        public static Faculty GetInstance() {
            _faculty = _faculty ?? new Faculty();
            return _faculty;
        }

        public BigInteger Calculate(BigInteger n) 
        {
            // check if input is smaller 0
            if (n < 0)
                throw new ArgumentException(" !!! Faculty is not defined for values < 0 !!!");

            // if value is not already calculated => do so
            if(!_values.ContainsKey(n))
                Faculties(n);

            // retrieve n! from Sorted List
            return _values[n];
        }

        private static void Faculties(BigInteger n)
        {
            // get the last calculated values and continue calculating if the calculation for a bigger n is required
            BigInteger i = _values.Max(x => x.Key),
                           result = _values[i];

            while (++i <= n)
            {
                CalculateNext(ref result, i);
                // add value to the SortedList if not already done
                if (!_values.ContainsKey(i))
                    _values.Add(i, result);
            }
        }

        private static void CalculateNext(ref BigInteger lastresult, BigInteger i) {

            // put in whatever iterative calculation step you want to do
            lastresult = lastresult * i;

        }
    }
}

Sedangkan untuk Scala, Anda dapat menambahkan @tailrecanotasi ke metode rekursif. Dengan cara ini kompiler memastikan bahwa optimasi panggilan ekor benar-benar terjadi:

Jadi ini tidak akan dikompilasi (faktorial):

@tailrec
def fak1(n: Int): Int = {
  n match {
    case 0 => 1
    case _ => n * fak1(n - 1)
  }
}

pesan kesalahannya adalah:

scala: tidak bisa mengoptimalkan @tailrec metode beranotasi fak1: ini berisi panggilan rekursif yang tidak dalam posisi ekor

Di samping itu:

def fak3(n: Int): Int = {
  @tailrec
  def fak3(n: Int, result: Int): Int = {
    n match {
      case 0 => result
      case _ => fak3(n - 1, n * result)
    }
  }

  fak3(n, 1)
}

kompilasi, dan optimasi panggilan ekor dilakukan.

Salah satu kemungkinan yang belum disebutkan adalah memiliki rekursi, tetapi tanpa menggunakan tumpukan sistem. Tentu saja Anda dapat meluap tumpukan Anda juga, tetapi jika algoritma Anda benar-benar perlu mundur dalam satu bentuk atau yang lain (mengapa menggunakan rekursi sama sekali?), Anda tidak punya pilihan.

Ada implementasi stackless dari beberapa bahasa, misalnya Stackless Python .

Solusi lain adalah mensimulasikan tumpukan Anda sendiri dan tidak bergantung pada implementasi compiler + runtime. Ini bukan solusi sederhana atau cepat, tetapi secara teoritis Anda akan mendapatkan StackOverflow hanya ketika Anda kehabisan memori.