Adakah yang bisa dilakukan dengan rekursi yang tidak bisa dilakukan dengan loop?

Ada saat-saat di mana menggunakan rekursi lebih baik daripada menggunakan loop, dan waktu di mana menggunakan loop lebih baik daripada menggunakan rekursi. Memilih yang "benar" dapat menghemat sumber daya dan / atau menghasilkan lebih sedikit baris kode.

Apakah ada kasus di mana tugas hanya dapat dilakukan dengan menggunakan rekursi, bukan loop?

Iya dan tidak. Pada akhirnya, tidak ada rekursi yang bisa menghitung perulangan itu tidak bisa, tetapi perulangan membutuhkan lebih banyak pipa ledeng. Oleh karena itu, satu hal yang dapat dilakukan rekursi agar loop tidak dapat membuat beberapa tugas menjadi sangat mudah.

Berjalanlah di pohon. Berjalan pohon dengan rekursi itu gampang-gampang susah. Itu hal yang paling alami di dunia. Berjalan pohon dengan loop jauh lebih mudah. Anda harus memelihara tumpukan atau struktur data lain untuk melacak apa yang telah Anda lakukan.

Seringkali, solusi rekursif untuk suatu masalah lebih cantik. Itu istilah teknis, dan itu penting.

Tidak.

Mendapatkan ke yang sangat dasar-dasar minimum yang diperlukan untuk menghitung, Anda hanya perlu untuk dapat lingkaran (ini saja tidak cukup, melainkan merupakan komponen yang diperlukan). Tidak masalah bagaimana caranya .

Bahasa pemrograman apa pun yang dapat menerapkan Mesin Turing, disebut Turing complete . Dan ada banyak bahasa yang turing lengkap.

Bahasa favorit saya di jalan di sana "yang benar-benar berfungsi?" Kelengkapan Turing adalah dari FRACTRAN , yang merupakan Turing lengkap . Ini memiliki satu struktur loop, dan Anda dapat menerapkan mesin Turing di dalamnya. Dengan demikian, apa pun yang dapat dihitung, dapat diimplementasikan dalam bahasa yang tidak memiliki rekursi. Oleh karena itu, tidak ada yang rekursi dapat berikan kepada Anda dalam hal komputabilitas yang tidak dapat dilakukan perulangan sederhana.

Ini sebenarnya bermuara pada beberapa poin:

• Apa pun yang dapat dihitung dapat dihitung pada mesin Turing
• Bahasa apa pun yang dapat mengimplementasikan mesin Turing (disebut Turing complete), dapat menghitung apa saja yang dapat dilakukan oleh bahasa lain
• Karena ada mesin Turing dalam bahasa yang tidak memiliki rekursi (dan ada yang lain yang hanya memiliki rekursi ketika Anda masuk ke beberapa esolang lainnya), maka tentu benar bahwa tidak ada yang dapat Anda lakukan dengan rekursi yang tidak dapat Anda lakukan dengan loop (dan tidak ada yang dapat Anda lakukan dengan loop yang tidak dapat Anda lakukan dengan rekursi).

Ini bukan untuk mengatakan bahwa ada beberapa kelas masalah yang lebih mudah dianggap dengan rekursi daripada dengan perulangan, atau dengan perulangan daripada dengan rekursi. Namun, alat-alat ini juga sama kuatnya.

Dan sementara saya mengambil ini ke 'esolang' ekstrim (kebanyakan karena Anda dapat menemukan hal-hal yang Turing lengkap dan diimplementasikan dengan cara yang agak aneh), ini tidak berarti bahwa esolang dengan cara apa pun opsional. Ada seluruh daftar hal-hal yang secara tidak sengaja lengkap Turing termasuk Magic the Gathering, Sendmail, templat MediaWiki, dan sistem jenis Scala. Banyak dari ini jauh dari optimal ketika datang untuk benar-benar melakukan sesuatu yang praktis, hanya saja Anda dapat menghitung apa pun yang dapat dihitung menggunakan alat-alat ini.

Kesetaraan ini bisa sangat menarik ketika Anda masuk ke jenis rekursi tertentu yang dikenal sebagai panggilan ekor .

Jika Anda memiliki, katakanlah, metode faktorial yang ditulis sebagai:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

Jenis rekursi ini akan ditulis ulang sebagai loop - tidak ada tumpukan yang digunakan. Pendekatan semacam itu memang seringkali lebih elegan dan lebih mudah dipahami daripada loop ekivalen yang ditulis, tetapi sekali lagi, untuk setiap panggilan rekursif dapat ada loop ekivalen yang ditulis dan untuk setiap loop dapat ada panggilan rekursif yang ditulis.

Ada juga saat-saat di mana mengubah loop sederhana menjadi panggilan rekursif panggilan ekor dapat berbelit-belit dan lebih sulit untuk dipahami.

Jika Anda ingin masuk ke sisi teori itu, lihat tesis Church Turing . Anda juga dapat menemukan tesis gereja-turing di CS.SE berguna.

Apakah ada kasus di mana tugas hanya dapat dilakukan dengan menggunakan rekursi, bukan loop?

Anda selalu dapat mengubah algoritme rekursif menjadi loop, yang menggunakan struktur data Last-In-First-Out (AKA stack) untuk menyimpan keadaan sementara, karena panggilan rekursif persis seperti itu, menyimpan keadaan saat ini dalam tumpukan, melanjutkan dengan algoritma, kemudian mengembalikan keadaan. Jadi jawaban singkatnya adalah: Tidak, tidak ada kasus seperti itu .

Namun, argumen dapat dibuat untuk "ya". Mari kita ambil contoh konkret dan mudah: merge sort. Anda perlu membagi data menjadi dua bagian, menggabungkan mengurutkan bagian-bagian, dan kemudian menggabungkannya. Bahkan jika Anda tidak melakukan panggilan fungsi bahasa pemrograman aktual untuk menggabungkan pengurutan untuk melakukan penggabungan pengurutan pada bagian-bagian, Anda perlu mengimplementasikan fungsionalitas yang identik dengan benar-benar melakukan pemanggilan fungsi (push state ke stack Anda sendiri, lompat ke mulai dari loop dengan parameter awal yang berbeda, kemudian muncul status dari stack Anda).

Apakah ini rekursi, jika Anda menerapkan panggilan rekursi itu sendiri, sebagai langkah "push state" yang terpisah dan "lompat ke awal" dan "pop state"? Dan jawabannya adalah: Tidak, itu masih tidak disebut rekursi, itu disebut iterasi dengan tumpukan eksplisit (jika Anda ingin menggunakan terminologi yang sudah mapan).

Catatan, ini juga tergantung pada definisi "tugas". Jika tugas adalah untuk mengurutkan, maka Anda dapat melakukannya dengan banyak algoritma, banyak di antaranya tidak memerlukan jenis rekursi apa pun. Jika tugas adalah mengimplementasikan algoritma spesifik, seperti penggabungan sortir, maka ambiguitas di atas berlaku.

Jadi mari kita perhatikan pertanyaan, apakah ada tugas umum, yang hanya ada algoritma rekursi. Dari komentar @WizardOfMenlo di bawah pertanyaan, fungsi Ackermann adalah contoh sederhana dari itu. Jadi konsep rekursi berdiri sendiri, bahkan jika itu dapat diimplementasikan dengan konstruksi program komputer yang berbeda (iterasi dengan stack eksplisit).

Itu tergantung pada seberapa ketat Anda mendefinisikan "rekursi".

Jika kita benar-benar mengharuskannya untuk melibatkan tumpukan panggilan (atau mekanisme apa pun untuk mempertahankan status program yang digunakan), maka kita selalu dapat menggantinya dengan sesuatu yang tidak. Memang, bahasa yang secara alami mengarah pada penggunaan rekursi yang berat cenderung memiliki kompiler yang menggunakan optimisasi panggilan ekor, sehingga apa yang Anda tulis bersifat rekursif tetapi apa yang Anda jalankan adalah berulang.

Namun mari kita pertimbangkan kasus di mana kita melakukan panggilan rekursif dan menggunakan hasil dari panggilan rekursif untuk panggilan rekursif itu.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Membuat iteratif panggilan rekursif pertama adalah mudah:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Kami kemudian dapat membersihkan menghapus gotountuk menangkal velociraptors dan bayangan Dijkstra:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Tetapi untuk menghapus panggilan rekursif lainnya, kita harus menyimpan nilai beberapa panggilan ke stack:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Sekarang, ketika kita mempertimbangkan kode sumber, kita tentu mengubah metode rekursif kita menjadi yang berulang.

Mempertimbangkan apa yang telah dikompilasi, kami telah mengubah kode yang menggunakan panggilan stack untuk mengimplementasikan rekursi ke dalam kode yang tidak (dan dalam melakukannya mengubah kode yang akan membuang pengecualian stack-overflow bahkan untuk nilai yang sangat kecil ke dalam kode yang hanya akan butuh waktu yang sangat lama untuk kembali [lihat Bagaimana saya bisa mencegah fungsi Ackerman saya meluap tumpukan? untuk beberapa optimisasi lebih lanjut yang membuatnya benar-benar kembali untuk banyak input yang lebih mungkin]).

Mempertimbangkan bagaimana rekursi diimplementasikan secara umum, kami telah mengubah kode yang menggunakan panggilan-tumpukan menjadi kode yang menggunakan tumpukan yang berbeda untuk menahan operasi yang tertunda. Karena itu kita dapat berpendapat bahwa itu masih bersifat rekursif, ketika dipertimbangkan pada tingkat rendah itu.

Dan pada level itu, memang tidak ada cara lain di sekitarnya. Jadi jika Anda menganggap metode itu sebagai rekursif, maka memang ada hal-hal yang tidak dapat kita lakukan tanpanya. Meskipun secara umum kami tidak memberi label kode semacam itu sebagai rekursif. Istilah rekursi berguna karena mencakup serangkaian pendekatan tertentu dan memberi kita cara untuk membicarakannya, dan kita tidak lagi menggunakan salah satunya.

Tentu saja, semua ini mengasumsikan Anda punya pilihan. Ada kedua bahasa yang melarang panggilan rekursif, dan bahasa yang tidak memiliki struktur pengulangan yang diperlukan untuk iterasi.

Jawaban klasiknya adalah "tidak", tetapi izinkan saya untuk menjelaskan mengapa saya berpikir "ya" adalah jawaban yang lebih baik.

Sebelum melanjutkan, mari kita dapatkan sesuatu: dari sudut pandang komputabilitas & kompleksitas:

• Jawabannya adalah "tidak" jika Anda diizinkan memiliki tumpukan tambahan saat mengulang.
• Jawabannya adalah "ya" jika Anda tidak diizinkan data tambahan saat perulangan.

Oke, sekarang, mari kita meletakkan satu kaki di tanah praktik, menjaga kaki lainnya di tanah teori.

Tumpukan panggilan adalah struktur kontrol , sedangkan tumpukan manual adalah struktur data . Kontrol dan data bukanlah konsep yang sama, tetapi mereka setara dalam arti bahwa mereka dapat direduksi satu sama lain (atau "ditiru" satu sama lain) dari sudut pandang komputabilitas atau kompleksitas.

Kapan perbedaan ini penting? Ketika Anda bekerja dengan alat dunia nyata. Ini sebuah contoh:

Katakanlah Anda menerapkan N-way mergesort. Anda mungkin memiliki forloop yang melewati masing-masing Nsegmen, memanggil mergesortmereka secara terpisah, kemudian menggabungkan hasilnya.

Bagaimana Anda memparalelkan ini dengan OpenMP?

Di bidang rekursif, ini sangat sederhana: cukup letakkan #pragma omp parallel forlingkaran Anda yang bergerak dari 1 ke N, dan Anda selesai. Di ranah iteratif, Anda tidak bisa melakukan ini. Anda harus menelurkan utas secara manual dan memberikan data yang sesuai secara manual sehingga mereka tahu apa yang harus dilakukan.

Di sisi lain, ada alat lain (seperti vektorizers otomatis, misalnya #pragma vector) yang bekerja dengan loop tetapi sama sekali tidak berguna dengan rekursi.

Intinya, hanya karena Anda dapat membuktikan kedua paradigma itu setara secara matematis, itu tidak berarti mereka sama dalam praktik. Masalah yang mungkin sepele untuk diotomatisasi dalam satu paradigma (katakanlah, paralelisasi loop) mungkin jauh lebih sulit untuk diselesaikan dalam paradigma lain.

yaitu: Alat untuk satu paradigma tidak secara otomatis diterjemahkan ke paradigma lain.

Akibatnya, jika Anda memerlukan alat untuk memecahkan masalah, kemungkinan alat tersebut hanya akan bekerja dengan satu jenis pendekatan tertentu, dan akibatnya Anda akan gagal menyelesaikan masalah dengan pendekatan yang berbeda, bahkan jika Anda dapat membuktikan secara matematis masalah tersebut dapat dipecahkan dengan cara baik.

Mengesampingkan alasan teoretis, mari kita lihat seperti apa rekursi dan loop dari sudut pandang mesin (perangkat keras atau virtual). Rekursi adalah kombinasi dari aliran kontrol yang memungkinkan untuk memulai eksekusi beberapa kode dan untuk kembali pada penyelesaian (dalam tampilan sederhana ketika sinyal dan pengecualian diabaikan) dan data yang diteruskan ke kode lain (argumen) dan yang dikembalikan dari itu (hasil). Biasanya tidak ada manajemen memori eksplisit yang terlibat, namun ada alokasi implisit memori stack untuk menyimpan alamat, argumen, hasil dan data lokal menengah.

Loop adalah kombinasi aliran kontrol dan data lokal. Membandingkan ini dengan rekursi, kita dapat melihat bahwa jumlah data dalam kasus ini adalah tetap. Satu-satunya cara untuk memecahkan batasan ini adalah dengan menggunakan memori dinamis (juga dikenal sebagai heap ) yang dapat dialokasikan (dan dibebaskan) kapan pun diperlukan.

Untuk meringkas:

• Kasing rekursi = Aliran kontrol + Stack (+ Heap)
• Kasus lingkaran = Aliran kontrol + Heap

Dengan asumsi bahwa bagian aliran kontrol cukup kuat, satu-satunya perbedaan adalah pada tipe memori yang tersedia. Jadi, kita dibiarkan dengan 4 case (kekuatan ekspresif terdaftar dalam tanda kurung):

1. Tidak ada tumpukan, tidak ada tumpukan: rekursi dan struktur dinamis tidak mungkin. (rekursi = loop)
2. Stack, no heap: rekursi OK, struktur dinamis tidak mungkin. (rekursi> lingkaran)
3. Tidak ada tumpukan, tumpukan: rekursi tidak mungkin, struktur dinamis OK. (rekursi = loop)
4. Stack, heap: rekursi dan struktur dinamis OK. (rekursi = loop)

Jika aturan mainnya sedikit lebih ketat dan implementasi rekursif tidak diizinkan untuk menggunakan loop, kita malah mendapatkan ini:

1. Tidak ada tumpukan, tidak ada tumpukan: rekursi dan struktur dinamis tidak mungkin. (rekursi <loop)
2. Stack, no heap: rekursi OK, struktur dinamis tidak mungkin. (rekursi> lingkaran)
3. Tidak ada tumpukan, tumpukan: rekursi tidak mungkin, struktur dinamis OK. (rekursi <loop)
4. Stack, heap: rekursi dan struktur dinamis OK. (rekursi = loop)

Perbedaan utama dengan skenario sebelumnya adalah kurangnya memori stack tidak memungkinkan rekursi tanpa loop untuk melakukan lebih banyak langkah selama eksekusi daripada ada baris kode.

Iya. Ada beberapa tugas umum yang mudah diselesaikan menggunakan rekursi tetapi tidak mungkin hanya dengan loop:

• Menyebabkan tumpukan meluap.
• Pemrogram pemula yang benar-benar membingungkan.
• Membuat fungsi yang tampak cepat yang sebenarnya adalah O (n ^ n).

Ada perbedaan antara fungsi rekursif dan fungsi rekursif primitif. Fungsi rekursif primitif adalah fungsi yang dihitung menggunakan loop, di mana jumlah iterasi maksimum setiap loop dihitung sebelum eksekusi loop dimulai. (Dan "rekursif" di sini tidak ada hubungannya dengan penggunaan rekursi).

Fungsi rekursif primitif benar-benar kurang kuat daripada fungsi rekursif. Anda akan mendapatkan hasil yang sama jika Anda mengambil fungsi yang menggunakan rekursi, di mana kedalaman maksimum rekursi harus dihitung sebelumnya.

Jika Anda memprogram dalam c ++, dan menggunakan c ++ 11, maka ada satu hal yang harus dilakukan dengan menggunakan rekursi: fungsi constexpr. Tetapi standar membatasi ini hingga 512, seperti yang dijelaskan dalam jawaban ini . Menggunakan loop dalam hal ini tidak mungkin, karena dalam kasus ini fungsi tidak bisa menjadi constexpr, tetapi ini diubah dalam c ++ 14.

• Jika panggilan rekursif adalah pernyataan pertama atau terakhir (tidak termasuk pengecekan kondisi) dari fungsi rekursif, cukup mudah untuk diterjemahkan ke dalam struktur pengulangan.
• Tetapi jika fungsi melakukan beberapa hal lain sebelum dan sesudah panggilan rekursif , maka akan sulit untuk mengubahnya menjadi loop.
• Jika fungsinya memiliki beberapa panggilan rekursif, mengonversinya menjadi kode yang hanya menggunakan loop akan sangat tidak mungkin. Beberapa tumpukan akan diperlukan untuk mengikuti data. Dalam rekursi tumpukan panggilan itu sendiri akan berfungsi sebagai tumpukan data.

Saya setuju dengan pertanyaan lain. Tidak ada yang dapat Anda lakukan dengan rekursi yang tidak dapat Anda lakukan dengan satu lingkaran.

TETAPI , menurut saya rekursi bisa sangat berbahaya. Pertama, bagi sebagian orang lebih sulit untuk memahami apa yang sebenarnya terjadi dalam kode. Kedua, setidaknya untuk C ++ (Java saya tidak yakin) setiap langkah rekursi berdampak pada memori karena setiap pemanggilan metode menyebabkan akumulasi memori dan inisialisasi header metode. Dengan cara ini Anda dapat meledakkan tumpukan Anda. Cukup coba rekursi angka Fibonacci dengan nilai input tinggi.