Apakah ada hit kinerja jika kita menggunakan loop bukan rekursi atau sebaliknya dalam algoritma di mana keduanya dapat melayani tujuan yang sama? Contoh: Periksa apakah string yang diberikan adalah palindrome. Saya telah melihat banyak programmer menggunakan rekursi sebagai sarana untuk pamer ketika algoritma iterasi sederhana dapat sesuai dengan tagihan. Apakah kompiler memainkan peran penting dalam memutuskan apa yang akan digunakan?

Ada kemungkinan rekursi akan lebih mahal, tergantung pada apakah fungsi rekursif adalah rekursif ekor (baris terakhir adalah panggilan rekursif). Rekursi ekor harus dikenali oleh kompiler dan dioptimalkan ke mitra berulangnya (sambil mempertahankan implementasi singkat dan jelas yang Anda miliki dalam kode Anda).

Saya akan menulis algoritma dengan cara yang paling masuk akal dan paling jelas bagi pengisap miskin (baik itu sendiri atau orang lain) yang harus mempertahankan kode dalam beberapa bulan atau tahun. Jika Anda mengalami masalah kinerja, kemudian buat profil kode Anda, dan kemudian dan kemudian optimalkan dengan beralih ke implementasi berulang. Anda mungkin ingin melihat ke dalam memoisasi dan pemrograman dinamis .

Loop dapat mencapai perolehan kinerja untuk program Anda. Rekursi dapat mencapai perolehan kinerja untuk programmer Anda. Pilih yang lebih penting dalam situasi Anda!

Membandingkan rekursi dengan iterasi adalah seperti membandingkan obeng kepala phillips dengan obeng kepala datar. Sebagian besar Anda dapat melepas sekrup kepala phillips dengan kepala datar, tetapi akan lebih mudah jika Anda menggunakan obeng yang dirancang untuk sekrup itu, bukan?

Beberapa algoritma hanya memungkinkan untuk rekursi karena cara mereka dirancang (Urutan Fibonacci, melintasi struktur seperti pohon, dll.). Rekursi membuat algoritme lebih ringkas dan lebih mudah dipahami (karena itu dapat dibagikan dan digunakan kembali).

Juga, beberapa algoritma rekursif menggunakan "Evaluasi Malas" yang membuatnya lebih efisien daripada saudara berulang mereka. Ini berarti bahwa mereka hanya melakukan perhitungan mahal pada saat mereka diperlukan daripada setiap kali loop berjalan.

Itu sudah cukup untuk membantu Anda memulai. Saya akan menggali beberapa artikel dan contoh untuk Anda juga.

Tautan 1: Haskel vs PHP (Rekursi vs Iterasi)

Berikut adalah contoh di mana programmer harus memproses kumpulan data besar menggunakan PHP. Dia menunjukkan betapa mudahnya menangani di Haskel menggunakan rekursi, tetapi karena PHP tidak memiliki cara mudah untuk mencapai metode yang sama, ia terpaksa menggunakan iterasi untuk mendapatkan hasilnya.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Tautan 2: Menguasai Rekursi

Sebagian besar reputasi buruk rekursi berasal dari biaya tinggi dan inefisiensi dalam bahasa imperatif. Penulis artikel ini berbicara tentang bagaimana mengoptimalkan algoritma rekursif untuk membuatnya lebih cepat dan lebih efisien. Dia juga membahas cara mengubah loop tradisional menjadi fungsi rekursif dan manfaat menggunakan rekursi ujung-ekor. Kata-kata penutupnya benar-benar merangkum beberapa poin kunci saya, saya pikir:

"pemrograman rekursif memberi programmer cara yang lebih baik untuk mengatur kode dengan cara yang dapat dipertahankan dan konsisten secara logis."

https://developer.ibm.com/articles/l-recurs/

Tautan 3: Apakah rekursi lebih cepat daripada perulangan? (Menjawab)

Berikut adalah tautan ke jawaban untuk pertanyaan stackoverflow yang serupa dengan Anda. Penulis menunjukkan bahwa banyak tolok ukur yang terkait dengan pengulangan atau pengulangan sangat spesifik dalam bahasa. Bahasa imperatif biasanya lebih cepat menggunakan loop dan lebih lambat dengan rekursi dan sebaliknya untuk bahasa fungsional. Saya kira poin utama yang harus diambil dari tautan ini adalah bahwa sangat sulit untuk menjawab pertanyaan dalam bahasa agnostik / situasi buta akal.

Apakah rekursi lebih cepat daripada perulangan?

Rekursi lebih mahal dalam memori, karena setiap panggilan rekursif umumnya membutuhkan alamat memori untuk didorong ke stack - sehingga nanti program dapat kembali ke titik itu.

Namun, ada banyak kasus di mana rekursi jauh lebih alami dan mudah dibaca daripada loop - seperti ketika bekerja dengan pohon. Dalam kasus ini saya akan merekomendasikan tetap pada rekursi.

Biasanya, orang akan mengharapkan penalti kinerja berada di arah yang lain. Panggilan rekursif dapat menyebabkan pembangunan frame stack ekstra; hukuman untuk ini bervariasi. Selain itu, dalam beberapa bahasa seperti Python (lebih tepatnya, dalam beberapa implementasi beberapa bahasa ...), Anda dapat menjalankan ke batas tumpukan dengan lebih mudah untuk tugas yang mungkin Anda tentukan secara rekursif, seperti menemukan nilai maksimum dalam struktur data pohon. Dalam kasus ini, Anda benar-benar ingin tetap menggunakan loop.

Menulis fungsi rekursif yang baik dapat sedikit mengurangi penalti kinerja, dengan asumsi Anda memiliki kompiler yang mengoptimalkan rekursi ekor, dll. (Periksa juga untuk memastikan bahwa fungsi tersebut benar-benar rekursif ekor --- itu adalah salah satu hal yang banyak orang membuat kesalahan. di.)

Terlepas dari kasus "tepi" (komputasi kinerja tinggi, kedalaman rekursi yang sangat besar, dll.), Lebih baik untuk mengadopsi pendekatan yang paling jelas menyatakan niat Anda, dirancang dengan baik, dan dapat dipertahankan. Optimalkan hanya setelah mengidentifikasi suatu kebutuhan.

Rekursi lebih baik daripada iterasi untuk masalah yang dapat dipecah menjadi beberapa bagian yang lebih kecil.

Misalnya, untuk membuat algoritma Fibonnaci rekursif, Anda memecah fib (n) menjadi fib (n-1) dan fib (n-2) dan menghitung kedua bagian. Iterasi hanya memungkinkan Anda untuk mengulangi satu fungsi berulang-ulang.

Namun, Fibonacci sebenarnya adalah contoh rusak dan saya pikir iterasi sebenarnya lebih efisien. Perhatikan bahwa fib (n) = fib (n-1) + fib (n-2) dan fib (n-1) = fib (n-2) + fib (n-3). fib (n-1) akan dihitung dua kali!

Contoh yang lebih baik adalah algoritma rekursif untuk pohon. Masalah menganalisis simpul orangtua dapat dipecah menjadi beberapa masalah kecil menganalisis setiap simpul anak. Berbeda dengan contoh Fibonacci, masalah yang lebih kecil tidak tergantung satu sama lain.

Jadi ya - rekursi lebih baik daripada iterasi untuk masalah yang dapat dipecah menjadi beberapa, lebih kecil, independen, masalah serupa.

Kinerja Anda memburuk saat menggunakan rekursi karena memanggil metode, dalam bahasa apa pun, menyiratkan banyak persiapan: kode panggilan mem-posting alamat pengirim, parameter panggilan, beberapa informasi konteks lain seperti register prosesor mungkin disimpan di suatu tempat, dan pada waktu kembali disebut metode memposting nilai kembali yang kemudian diambil oleh pemanggil, dan informasi konteks apa pun yang sebelumnya disimpan akan dikembalikan. perbedaan kinerja antara pendekatan berulang dan rekursif terletak pada waktu operasi ini dilakukan.

Dari sudut pandang implementasi, Anda benar-benar mulai memperhatikan perbedaannya ketika waktu yang dibutuhkan untuk menangani konteks panggilan sebanding dengan waktu yang diperlukan metode Anda untuk mengeksekusi. Jika metode rekursif Anda membutuhkan waktu lebih lama untuk dieksekusi daripada bagian manajemen konteks panggilan, lanjutkan dengan cara rekursif karena kode ini umumnya lebih mudah dibaca dan mudah dipahami dan Anda tidak akan melihat kehilangan kinerja. Kalau tidak pergi berulang untuk alasan efisiensi.

Saya percaya rekursi ekor di java saat ini tidak dioptimalkan. Detailnya disebarkan sepanjang diskusi ini tentang LtU dan tautan terkait. Ini mungkin fitur di versi 7 yang akan datang, tetapi rupanya itu menghadirkan kesulitan tertentu ketika dikombinasikan dengan Stack Inspection karena bingkai tertentu akan hilang. Stack Inspection telah digunakan untuk mengimplementasikan model keamanan berbutir halus mereka sejak Java 2.

http://lambda-the-ultimate.org/node/1333

Ada banyak kasus di mana ia memberikan solusi yang jauh lebih elegan daripada metode iteratif, contoh umum adalah traversal dari pohon biner, jadi itu tidak selalu lebih sulit untuk dipelihara. Secara umum, versi berulang biasanya sedikit lebih cepat (dan selama optimasi mungkin menggantikan versi rekursif), tetapi versi rekursif lebih mudah untuk dipahami dan diimplementasikan dengan benar.

Rekursi yang sangat berguna adalah beberapa situasi. Sebagai contoh, pertimbangkan kode untuk menemukan faktorial

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Sekarang pertimbangkan dengan menggunakan fungsi rekursif

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

Dengan mengamati kedua hal ini, kita dapat melihat bahwa rekursi mudah dipahami. Tetapi jika tidak digunakan dengan hati-hati itu bisa jadi banyak kesalahan juga. Misalkan jika kita ketinggalan if (input == 0), maka kode akan dieksekusi untuk beberapa waktu dan berakhir dengan stack overflow.

Dalam banyak kasus rekursi lebih cepat karena caching, yang meningkatkan kinerja. Sebagai contoh, di sini adalah versi iteratif dari gabungan jenis menggunakan rutin gabungan tradisional. Ini akan berjalan lebih lambat daripada implementasi rekursif karena caching peningkatan kinerja.

Implementasi berulang

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Implementasi rekursif

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - ini adalah apa yang diceritakan oleh Profesor Kevin Wayne (Princeton University) tentang kursus tentang algoritma yang disajikan pada Coursera.

Dengan menggunakan rekursi, Anda dikenai biaya pemanggilan fungsi dengan setiap "iterasi", sedangkan dengan perulangan, satu-satunya hal yang biasanya Anda bayar adalah kenaikan / penurunan. Jadi, jika kode untuk loop tidak jauh lebih rumit daripada kode untuk solusi rekursif, loop biasanya akan lebih unggul daripada rekursi.

Rekursi dan iterasi tergantung pada logika bisnis yang ingin Anda terapkan, meskipun dalam sebagian besar kasus dapat digunakan secara bergantian. Sebagian besar pengembang melakukan rekursi karena lebih mudah dipahami.

Itu tergantung pada bahasanya. Di Jawa Anda harus menggunakan loop. Bahasa fungsional mengoptimalkan rekursi.

Jika Anda hanya mengulangi daftar, maka yakinkan, beralihlah.

Beberapa jawaban lain telah menyebutkan traversal pohon (kedalaman-pertama). Ini benar-benar contoh yang bagus, karena itu adalah hal yang sangat umum untuk dilakukan pada struktur data yang sangat umum. Rekursi sangat intuitif untuk masalah ini.

Lihat metode "temukan" di sini: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Rekursi lebih sederhana (dan karenanya - lebih mendasar) daripada definisi iterasi yang memungkinkan. Anda dapat mendefinisikan sistem Turing-complete dengan hanya sepasang combinator (ya, bahkan rekursi itu sendiri adalah gagasan turunan dalam sistem semacam itu). Kalkulus Lambda adalah sistem fundamental yang sama kuatnya, menampilkan fungsi rekursif. Tetapi jika Anda ingin mendefinisikan iterasi dengan benar, Anda akan membutuhkan lebih banyak primitif untuk memulai.

Adapun kode - tidak, kode rekursif sebenarnya jauh lebih mudah dipahami dan dipelihara daripada yang iteratif murni, karena sebagian besar struktur data bersifat rekursif. Tentu saja, untuk memperbaikinya orang perlu bahasa dengan dukungan untuk fungsi dan penutupan tingkat tinggi, setidaknya - untuk mendapatkan semua kombinator standar dan iterator dengan cara yang rapi. Dalam C ++, tentu saja, solusi rekursif yang rumit dapat terlihat agak jelek, kecuali jika Anda adalah pengguna hardcore FC ++ dan sejenisnya.

Saya akan berpikir dalam rekursi (non-ekor) akan ada hit kinerja untuk mengalokasikan tumpukan baru dll setiap kali fungsi dipanggil (tergantung pada bahasa tentu saja).

itu tergantung pada "kedalaman rekursi". itu tergantung pada seberapa banyak fungsi panggilan overhead akan mempengaruhi total waktu eksekusi.

Misalnya, menghitung faktorial klasik dengan cara rekursif sangat tidak efisien karena: - risiko data meluap - risiko stack overflowing - panggilan fungsi overhead menempati 80% waktu eksekusi

sambil mengembangkan algoritma min-max untuk analisis posisi dalam permainan catur yang akan menganalisis gerakan N selanjutnya dapat diimplementasikan dalam rekursi atas "kedalaman analisis" (seperti yang saya lakukan ^ _ ^)

Pengulangan? Di mana saya mulai, wiki akan memberi tahu Anda "ini adalah proses pengulangan barang dengan cara yang mirip"

Kembali pada hari ketika saya sedang melakukan C, rekursi C ++ adalah mengirim dewa, hal-hal seperti "rekursi ekor". Anda juga akan menemukan banyak algoritma pengurutan yang menggunakan rekursi. Contoh pengurutan cepat: http://alienryderflex.com/quicksort/

Rekursi sama seperti algoritma lainnya yang berguna untuk masalah tertentu. Mungkin Anda mungkin tidak menemukan penggunaan langsung atau sering tetapi akan ada masalah Anda akan senang itu tersedia.

Dalam C ++ jika fungsi rekursif adalah templated, maka kompiler memiliki lebih banyak kesempatan untuk mengoptimalkannya, karena semua pengurangan tipe dan instantiasi fungsi akan terjadi dalam waktu kompilasi. Kompiler modern juga dapat menguraikan fungsi jika memungkinkan. Jadi jika seseorang menggunakan flag optimisasi suka -O3atau -O2dalam g++, maka rekursi mungkin memiliki kesempatan untuk lebih cepat daripada iterasi. Dalam kode iteratif, kompiler mendapat lebih sedikit kesempatan untuk mengoptimalkannya, karena sudah dalam keadaan lebih atau kurang optimal (jika ditulis dengan cukup baik).

Dalam kasus saya, saya mencoba mengimplementasikan matriks eksponensial dengan mengkuadratkan menggunakan objek matriks Armadillo, baik secara rekursif maupun iteratif. Algoritma dapat ditemukan di sini ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Fungsi saya templated dan saya telah menghitung 1,000,000 12x12matriks dinaikkan ke kekuasaan 10. Saya mendapat hasil sebagai berikut:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Hasil ini telah diperoleh dengan menggunakan gcc-4.8 dengan c ++ 11 flag ( -std=c++11) dan Armadillo 6.1 dengan Intel mkl. Kompiler Intel juga menunjukkan hasil yang serupa.

Mike benar. Rekursi ekor tidak dioptimalkan oleh Java compiler atau JVM. Anda akan selalu mendapatkan stack overflow dengan sesuatu seperti ini:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Anda harus ingat bahwa menggunakan rekursi yang terlalu dalam Anda akan mengalami Stack Overflow, tergantung pada ukuran stack yang diperbolehkan. Untuk mencegah hal ini, pastikan untuk menyediakan beberapa kasing dasar yang mengakhiri rekursi Anda.

Rekursi memiliki kelemahan bahwa algoritma yang Anda tulis menggunakan rekursi memiliki kompleksitas ruang O (n). Sementara pendekatan berulang memiliki kompleksitas ruang O (1). Ini adalah keuntungan menggunakan iterasi lebih dari rekursi. Lalu mengapa kita menggunakan rekursi?

Lihat di bawah.

Kadang-kadang lebih mudah untuk menulis suatu algoritma menggunakan rekursi sementara itu sedikit lebih sulit untuk menulis algoritma yang sama menggunakan iterasi. Dalam hal ini jika Anda memilih untuk mengikuti pendekatan iterasi Anda harus menangani tumpukan sendiri.

Jika iterasi bersifat atomik dan urutan besarnya lebih mahal daripada mendorong bingkai tumpukan baru dan membuat utas baru dan Anda memiliki banyak inti dan lingkungan runtime Anda dapat menggunakan semuanya, maka pendekatan rekursif dapat menghasilkan peningkatan kinerja yang sangat besar bila dikombinasikan dengan multithreading. Jika jumlah rata-rata iterasi tidak dapat diprediksi, maka mungkin ide yang baik untuk menggunakan kumpulan utas yang akan mengontrol alokasi utas dan mencegah proses Anda dari membuat terlalu banyak utas dan memonopoli sistem.

Misalnya, dalam beberapa bahasa, ada implementasi multitreaded merge sort yang rekursif.

Tetapi sekali lagi, multithreading dapat digunakan dengan looping daripada rekursi, jadi seberapa baik kombinasi ini akan bekerja tergantung pada lebih banyak faktor termasuk OS dan mekanisme alokasi utasnya.

Sejauh yang saya tahu, Perl tidak mengoptimalkan panggilan rekursif, tetapi Anda bisa memalsukannya.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

Saat pertama kali dipanggil itu akan mengalokasikan ruang pada stack. Kemudian ia akan mengubah argumennya, dan memulai kembali subrutin, tanpa menambahkan apa-apa lagi ke stack. Karena itu ia akan berpura-pura bahwa ia tidak pernah menyebut dirinya, mengubahnya menjadi proses berulang.

Perhatikan bahwa tidak ada " my @_;" atau " local @_;", jika Anda melakukannya tidak akan berfungsi lagi.

Dengan hanya menggunakan Chrome 45.0.2454.85 m, rekursi nampaknya merupakan jumlah yang bagus lebih cepat.

Ini kodenya:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

HASIL

// 100 berjalan menggunakan standar untuk loop

100x untuk menjalankan loop. Waktu untuk menyelesaikan: 7.683ms

// 100 berjalan menggunakan pendekatan rekursif fungsional dengan rekursi ekor

100x menjalankan rekursi. Waktu untuk menyelesaikan: 4.841ms

Pada tangkapan layar di bawah ini, rekursi menang lagi dengan selisih lebih besar ketika dijalankan pada 300 siklus per tes

Saya menemukan perbedaan lain antara pendekatan-pendekatan itu. Ini terlihat sederhana dan tidak penting, tetapi memiliki peran yang sangat penting saat Anda mempersiapkan wawancara dan masalah ini muncul, jadi perhatikan dengan cermat.

Singkatnya: 1) traversal post-order iteratif tidak mudah - yang membuat DFT lebih kompleks 2) siklus memeriksa lebih mudah dengan rekursi

Detail:

Dalam kasus rekursif, mudah untuk membuat travers pre dan post:

Bayangkan sebuah pertanyaan standar: "cetak semua tugas yang harus dieksekusi untuk menjalankan tugas 5, ketika tugas bergantung pada tugas lain"

Contoh:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Perhatikan bahwa post-order-traversal rekursif tidak memerlukan pembalikan hasil berikutnya. Anak-anak dicetak pertama dan tugas Anda dalam pertanyaan dicetak terakhir. Semuanya baik-baik saja. Anda dapat melakukan pra-pemesanan-traversal rekursif (juga ditunjukkan di atas) dan yang satu akan memerlukan pembalikan daftar hasil.

Tidak sesederhana itu dengan pendekatan berulang! Dalam pendekatan iteratif (satu tumpukan) Anda hanya dapat melakukan pra-pemesanan-traversal, sehingga Anda wajib membalikkan array hasil di akhir:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Terlihat sederhana, bukan?

Tapi itu adalah jebakan dalam beberapa wawancara.

Ini berarti yang berikut: dengan pendekatan rekursif, Anda dapat mengimplementasikan Depth First Traversal dan kemudian memilih pesanan apa yang Anda butuhkan sebelum atau sesudahnya (hanya dengan mengubah lokasi "cetak", dalam kasus kami "menambahkan ke daftar hasil" ). Dengan pendekatan berulang (satu tumpukan) Anda dapat dengan mudah melakukan hanya pre-order traversal dan dalam situasi ketika anak-anak perlu dicetak terlebih dahulu (hampir semua situasi ketika Anda perlu mulai mencetak dari node bawah, naik ke atas) - Anda berada di masalah. Jika Anda memiliki masalah itu, Anda dapat membalikkannya nanti, tetapi itu akan menjadi tambahan untuk algoritma Anda. Dan jika pewawancara melihat arlojinya, itu mungkin menjadi masalah bagi Anda. Ada cara-cara kompleks untuk melakukan traversal post-order berulang, mereka ada, tetapi mereka tidak sederhana . Contoh:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Jadi, intinya: Saya akan menggunakan rekursi selama wawancara, lebih mudah untuk mengelola dan menjelaskan. Anda memiliki cara yang mudah untuk beralih dari traversal pra ke post-order dalam kasus mendesak apa pun. Dengan iteratif Anda tidak sefleksibel itu.

Saya akan menggunakan rekursi dan kemudian mengatakan: "Ok, tapi iteratif dapat memberi saya kontrol lebih langsung pada memori yang digunakan, saya dapat dengan mudah mengukur ukuran stack dan melarang beberapa overflow berbahaya .."

Kelebihan lain dari rekursi - lebih mudah untuk menghindari / memperhatikan siklus dalam grafik.

Contoh (preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Mungkin menyenangkan untuk menuliskannya sebagai rekursi, atau sebagai praktik.

Namun, jika kode ini digunakan dalam produksi, Anda perlu mempertimbangkan kemungkinan stack overflow.

Optimasi rekursi tail dapat menghilangkan stack overflow, tetapi apakah Anda ingin melalui kesulitan membuatnya, dan Anda perlu tahu bahwa Anda dapat mengandalkan optimasi di lingkungan Anda.

Setiap kali algoritma berulang, berapa ukuran data atau n dikurangi dengan?

Jika Anda mengurangi ukuran data atau nsetengah setiap kali Anda muncul kembali, maka secara umum Anda tidak perlu khawatir tentang stack overflow. Katakanlah, jika perlu 4.000 level deep atau 10.000 level deep untuk program untuk stack overflow, maka ukuran data Anda harus sekitar 2 ⁴⁰⁰⁰ untuk program Anda untuk stack overflow. Untuk menempatkannya dalam perspektif, perangkat penyimpanan terbesar baru-baru ini dapat menampung 2 ⁶¹ byte, dan jika Anda memiliki 2 ⁶¹ perangkat tersebut, Anda hanya berurusan dengan 2 ¹²² ukuran data. Jika Anda melihat semua atom di alam semesta, diperkirakan jumlahnya mungkin kurang dari 2 ⁸⁴. Jika Anda perlu berurusan dengan semua data di alam semesta dan statusnya untuk setiap milidetik sejak kelahiran alam semesta diperkirakan 14 miliar tahun yang lalu, mungkin hanya 2 ¹⁵³ . Jadi, jika program Anda dapat menangani 2 ⁴⁰⁰⁰ (bilangan bulat 4000-bit), maka secara umum Anda tidak perlu khawatir tentang stack overflow.unit data atau n, Anda dapat menangani semua data di alam semesta dan program tidak akan menumpuk melimpah. Jika Anda tidak perlu berurusan dengan angka yang sebesar 2 ⁴⁰⁰⁰

Namun, jika Anda mengurangi ukuran data atau ndengan jumlah konstan setiap kali Anda kambuh, maka Anda dapat mengalami stack overflow ketika program Anda berjalan dengan baik ketika nada 1000tetapi dalam beberapa situasi, ketika nmenjadi hanya20000 .

Jadi jika Anda memiliki kemungkinan stack overflow, cobalah menjadikannya solusi berulang.

Saya akan menjawab pertanyaan Anda dengan merancang struktur data Haskell dengan "induksi", yang merupakan semacam "ganda" untuk rekursi. Dan kemudian saya akan menunjukkan bagaimana dualitas ini mengarah pada hal-hal yang menyenangkan.

Kami memperkenalkan jenis untuk pohon sederhana:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

Kita dapat membaca definisi ini dengan mengatakan "Pohon adalah Cabang (yang berisi dua pohon) atau daun (yang berisi nilai data)". Jadi daunnya adalah semacam case minimal. Jika pohon bukan daun, maka itu harus pohon majemuk yang mengandung dua pohon. Ini adalah satu-satunya kasus.

Mari kita membuat pohon:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Sekarang, misalkan kita ingin menambahkan 1 untuk setiap nilai di pohon. Kita dapat melakukan ini dengan menelepon:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

Pertama, perhatikan bahwa ini sebenarnya definisi rekursif. Dibutuhkan konstruktor data Branch and Leaf sebagai case (dan karena Leaf minimal dan ini adalah satu-satunya case yang mungkin), kami yakin bahwa fungsi tersebut akan berakhir.

Apa yang diperlukan untuk menulis addOne dengan gaya iteratif? Seperti apa bentuk lingkaran ke jumlah cabang yang berubah-ubah?

Juga, rekursi semacam ini sering dapat difaktorkan, dalam hal "functor". Kita bisa menjadikan Pohon menjadi Functors dengan mendefinisikan:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

dan mendefinisikan:

addOne' = fmap (+1)

Kami dapat memfaktorkan skema rekursi lainnya, seperti katamorfisme (atau lipatan) untuk tipe data aljabar. Dengan menggunakan katamorfisme, kita dapat menulis:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

Stack overflow hanya akan terjadi jika Anda memprogram dalam bahasa yang tidak ada dalam manajemen memori bawaan .... Jika tidak, pastikan Anda memiliki sesuatu di fungsi Anda (atau pemanggilan fungsi, STDLbs, dll.). Tanpa rekursi, tidak mungkin memiliki hal-hal seperti ... Google atau SQL, atau tempat mana pun yang harus disortir secara efisien melalui struktur data besar (kelas) atau basis data.

Rekursi adalah cara untuk pergi jika Anda ingin beralih melalui file, cukup yakin itulah caranya 'menemukan * | ? grep * berfungsi. Agak dual rekursi, terutama dengan pipa (tapi jangan melakukan banyak syscalls seperti banyak suka lakukan jika itu adalah sesuatu yang Anda akan meletakkan di luar sana untuk digunakan orang lain).

Bahasa tingkat yang lebih tinggi dan bahkan dentang / cpp dapat menerapkannya di latar belakang.