it-swarm-id.com

Rekursi atau Iterasi?

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?

210
Omnipotent

Mungkin saja rekursi akan lebih mahal, tergantung pada apakah fungsi rekursif adalah tail recursive (baris terakhir adalah panggilan rekursif). Ekor rekursi harus dikenali oleh kompiler dan dioptimalkan ke rekanan iteratifnya (sambil mempertahankan implementasi singkat dan jelas yang Anda miliki dalam kode Anda).

Saya akan menulis algoritme 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, maka buat profil kode Anda, dan kemudian dan kemudian optimalkan dengan beralih ke implementasi berulang. Anda mungkin ingin melihat ke memoisasi dan pemrograman dinamis .

176
Paul Osborne

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

309
Leigh Caldwell

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

Beberapa algoritma hanya meminjamkan diri untuk rekursi karena cara mereka dirancang (urutan Fibonacci, melintasi struktur seperti pohon, dll.). Rekursi membuat algoritma 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 dibutuhkan 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, dia 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? (Jawab)

Berikut adalah tautan ke jawaban untuk pertanyaan stackoverflow yang serupa dengan Anda. Penulis menunjukkan bahwa banyak tolok ukur yang terkait dengan pengulangan atau pengulangan adalah sangat spesifik 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?

76
Swift

Rekursi lebih mahal dalam memori, karena setiap panggilan rekursif umumnya memerlukan 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.

16
Doron Yaacoby

Biasanya, orang akan mengharapkan penalti kinerja berada di arah lain. Panggilan rekursif dapat menyebabkan pembangunan frame stack ekstra; hukuman untuk ini bervariasi. Juga, dalam beberapa bahasa seperti Python (lebih tepatnya, dalam beberapa implementasi beberapa bahasa ...), Anda dapat menjalankan ke dalam 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 anggapan 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 "Edge" (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.

11
zweiterlinde

Rekursi lebih baik daripada iterasi untuk masalah yang dapat dipecah menjadi beberapa, potongan 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 multipel masalah yang lebih 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.

8
Ben

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 balik yang kemudian diambil oleh pemanggil, dan informasi konteks apa pun yang sebelumnya disimpan akan dikembalikan. perbedaan kinerja antara pendekatan iteratif 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 karena alasan efisiensi.

7
entzik

Saya percaya rekursi ekor di Java saat ini tidak dioptimalkan. Detailnya ditaburkan di seluruh ini diskusi tentang LtU dan tautan terkait. Ini mungkin menjadi fitur di versi 7 yang akan datang, tetapi tampaknya ia 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/13

6
Mike Edwards

Dalam banyak kasus rekursi lebih cepat karena caching, yang meningkatkan kinerja. Sebagai contoh, berikut adalah versi iterasi 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.

5
Nikunj Banka

Ada banyak kasus di mana ia memberikan solusi yang jauh lebih elegan atas 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.

5
Felix

Rekursi yang sangat bermanfaat 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 menjadi sangat banyak kesalahan juga. Misalkan jika kita melewatkan if (input == 0), maka kode akan dieksekusi untuk beberapa waktu dan berakhir dengan biasanya stack overflow.

5
Harikrishnan

Itu tergantung pada bahasanya. Dalam Java Anda harus menggunakan loop. Bahasa fungsional mengoptimalkan rekursi.

4
mc

Dengan menggunakan rekursi, Anda dikenai biaya pemanggilan fungsi dengan setiap "iterasi", sedangkan dengan loop, 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.

4
MovEaxEsp

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.

4
Warrior

Rekursi lebih sederhana (dan karenanya - lebih mendasar) daripada definisi iterasi yang memungkinkan. Anda dapat mendefinisikan sistem Turing-complete dengan hanya sepasang kombinator (ya, bahkan rekursi itu sendiri adalah gagasan turunan dalam sistem semacam itu). Lambda kalkulus 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 murni iteratif, karena sebagian besar struktur data bersifat rekursif. Tentu saja, untuk memperbaikinya orang akan membutuhkan bahasa dengan dukungan untuk fungsi dan penutupan tingkat tinggi, setidaknya - untuk mendapatkan semua kombinator dan iterator standar dengan cara yang rapi. Dalam C++, tentu saja, solusi rekursif yang rumit dapat terlihat agak jelek, kecuali jika Anda adalah pengguna hardcore FC++ dan sama.

3
SK-logic

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

3
Joe Cheng

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

2
metadave

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 menampilkan fungsi jika memungkinkan. Jadi jika seseorang menggunakan flag optimisasi seperti -O3 atau -O2 di g++, maka rekursi mungkin memiliki kesempatan untuk menjadi 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 untuk mengimplementasikan eksponensiasi matriks dengan mengkuadratkan menggunakan objek matriks Armadillo, baik secara rekursif dan iteratif. Algoritma dapat ditemukan di sini ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Fungsi saya templated dan saya telah menghitung 1,000,00012x12 matriks dinaikkan ke daya 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.

2
Titas Chanda

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

2
Nickz

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 ^ _ ^)

2
ugasoft

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

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

Rekursi memiliki kelemahan bahwa algoritma yang Anda tulis menggunakan rekursi memiliki O(n) kompleksitas ruang. 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 sulit untuk menulis algoritma yang sama menggunakan iterasi. Dalam hal ini jika Anda memilih untuk mengikuti pendekatan iterasi Anda harus menangani tumpukan sendiri.

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.

1
Grigori A.

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 pun pada 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.

0
Brad Gilbert

Jika iterasinya atomik dan urutan besarnya lebih mahal daripada mendorong bingkai tumpukan baru dan membuat utas baru dan Anda memiliki banyak inti dan Anda Lingkungan runtime dapat menggunakan semuanya, maka pendekatan rekursif dapat menghasilkan peningkatan kinerja 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 multithreaded merge sort yang rekursif.

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

0
ccpizza

Menggunakan hanya 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

Recursion wins again!

0
Alpha G33k