Menghapus rekursi dengan Python

Halo, Habr! Saya hadir untuk Anda terjemahan artikel "Menghapus rekursi dengan Python, bagian 1" oleh Eric Lippert.

Selama 20 tahun terakhir, saya mengagumi kesederhanaan dan kekuatan Python, meskipun saya tidak pernah benar-benar bekerja dengannya atau belajar secara detail.

Baru-baru ini, saya telah memperhatikannya dengan seksama - dan itu ternyata menjadi bahasa yang sangat bagus.

Sebuah pertanyaan baru-baru ini tentang StackOverflow membuat saya bertanya-tanya bagaimana cara mengubah algoritma rekursif ke yang iteratif, dan ternyata Python adalah bahasa yang cukup bagus untuk ini.
Masalah yang ditemui penulis pertanyaan adalah sebagai berikut:

• Pemain berada di sel sewenang-wenang di bidang bernomor;
• Tujuannya adalah untuk kembali ke sel nomor 1;
• Jika pemain berada di kotak yang genap, ia membayar satu koin dan setengah jalan ke sel No. 1;
• Jika pemain berada di kotak yang aneh, ia dapat membayar 5 koin dan langsung ke kotak pertama atau membayar satu koin dan mengambil satu langkah ke kotak No. 1 - di kotak yang genap.

Pertanyaannya adalah: berapa jumlah koin terkecil yang harus Anda bayar untuk kembali dari sel saat ini ke yang pertama.

Tugas ini memiliki solusi rekursif yang jelas:

def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5) 

Namun, program ini macet, mencapai kedalaman maksimum rekursi, kemungkinan besar karena fakta bahwa penulis pertanyaan bereksperimen dengan jumlah yang sangat besar.
Oleh karena itu, muncul pertanyaan: bagaimana mengubah algoritma rekursif menjadi iteratif dengan Python?

Sebelum kita mulai, saya ingin mencatat bahwa tentu saja ada solusi yang lebih cepat untuk masalah khusus ini, itu sendiri tidak terlalu menarik.

Sebaliknya, tugas ini hanya berfungsi sebagai titik awal dalam pertanyaan tentang bagaimana, dalam kasus umum, untuk menyingkirkan panggilan rekursif tunggal dalam program Python.

Intinya adalah Anda dapat mengonversi metode rekursif sederhana dan menyingkirkan rekursi, dan ini hanyalah contoh yang sudah ada.

Teknik yang akan saya tunjukkan, tentu saja, tidak sama persis dengan cara Python ditulis, mungkin solusi gaya Python akan menggunakan generator atau fitur lain dari bahasa tersebut.

Apa yang ingin saya tunjukkan di sini adalah bagaimana menghilangkan rekursi menggunakan serangkaian transformasi kecil dan aman, memimpin fungsi ke bentuk di mana mudah untuk mengganti rekursi dengan iterasi.

Untuk memulai, mari kita lihat cara membawa program ke formulir ini.

Pada langkah pertama konversi kami, saya ingin perhitungan dilakukan sebelum panggilan rekursif dikurangi menjadi perhitungan argumen, dan perhitungan, setelah panggilan rekursif, harus dilakukan dalam metode terpisah yang menerima hasil panggilan rekursif.

 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result) 

Langkah kedua yang ingin saya buat adalah perhitungan argumen dalam fungsi terpisah:

 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result) 

Pada langkah ketiga, saya ingin menambahkan fungsi pembantu yang akan memilih fungsi kelanjutan yang dipanggil setelah kembali dari rekursi.

Perhatikan bahwa fungsi helper mengembalikan fungsi.

 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after  ! result = cost(argument) return after(result) 

Sekarang kita menulisnya dalam bentuk yang lebih umum dan ringkas:

 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument)) 

Dapat dilihat bahwa setiap perubahan tetap mempertahankan makna program.

Sekarang cek untuk paritas nomor dilakukan dua kali, meskipun sebelum perubahan ada satu cek.

Jika kita mau, kita bisa menyelesaikan masalah ini dengan menggabungkan dua fungsi pembantu menjadi satu yang mengembalikan tuple.

Tapi jangan khawatir tentang ini sebagai bagian dari tugas ini.

Kami telah mengurangi metode rekursif kami ke bentuk yang paling umum.

• Dalam kasus dasar:
  
  • menghitung nilai yang akan dikembalikan;
  • kembalikan.
• Dalam kasus non-dasar:
  
  • hitung argumen rekursi;
  • melakukan panggilan rekursif;
  • menghitung nilai pengembalian;
  • kembalikan.

Sesuatu yang penting yang perlu Anda perhatikan pada langkah ini adalah bahwa after itu tidak boleh mengandung panggilan cost itu sendiri.

Metode yang saya perlihatkan di sini menghilangkan satu panggilan rekursif.

Jika Anda memiliki 2 atau lebih rekursi, maka kami membutuhkan solusi yang berbeda.

Setelah kami membawa algoritma rekursif kami ke formulir ini, sudah mudah untuk mengubahnya menjadi berulang.

Kuncinya adalah membayangkan apa yang terjadi dalam program rekursif.

Bagaimana kami melakukan turunan rekursif: kami memanggil get_argument sebelum panggilan rekursif dan memanggil fungsi after setelah kembali dari rekursi.

Artinya, semua panggilan ke get_argument terjadi sebelum semua panggilan ke setelah .
Oleh karena itu, kita dapat mengonversikannya menjadi 2 siklus: panggilan pertama get_argument dan membentuk daftar fungsi setelah , dan panggilan kedua semua fungsi setelah :

 #... def cost(s): #     "after".    #       # ,    . afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument #       "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result 

Tidak ada lagi rekursi!

Kelihatannya seperti sulap, tetapi semua yang kita lakukan di sini adalah sama dengan versi rekursif dari program itu, dan dalam urutan yang sama.

Contoh ini mencerminkan pemikiran yang sering saya ulangi tentang tumpukan panggilan: tujuannya adalah untuk mengkomunikasikan apa yang akan terjadi selanjutnya, dan bukan apa yang sudah terjadi!

Satu-satunya informasi yang berguna pada stack panggilan dalam versi rekursif program adalah apa yang terjadi setelah masalah karena fungsi ini dipanggil berikutnya, dan segala sesuatu yang lain pada stack tidak penting.

Alih-alih menggunakan panggilan stack sebagai cara yang tidak efisien dan rumit untuk menyimpan after stack, kita bisa menyimpan fungsi after stack.

Lain kali kita akan melihat cara yang lebih kompleks untuk menghapus rekursi dengan Python.