Bagaimana cara memahami kode rekursi ini?

Saya menemukan kode ini dalam manual yang An Introduction to Programming in Emacs Lispmenunjukkan rekursi dengan bantuan condfungsi untuk mengetahui jumlah kerikil berdasarkan jumlah baris yang dimasukkan, yaitu jika baris = 2, maka kerikil harus 3, jika 4 baris maka harus 10 kerikil sana.

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

mengevaluasi sampai 10 setelah melewati argumen 4:

(triangle-using-cond 4)

Manual tidak menjelaskan dengan jelas apa yang terjadi pada setiap langkah dalam kode contoh ini khususnya dan saya tidak tahu bagaimana rekursi bekerja di sini. Dapatkah Anda membantu saya memahami mekanika langkah demi langkah apa yang terjadi pada setiap contoh?

Menggunakan "printf debugging"

Anda dapat membiarkan Emacs membantu Anda memahami dengan memodifikasi definisi fungsi:

(defun triangle-using-cond (number)
  (message (format "called with %d" number))
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Cukup tambahkan (message ...)tempat untuk membuat jejak dicetak ke *Messages*buffer.

Menggunakan Edebug

Tempatkan titik di mana saja di dalam definisi fungsi dan tekan C-u C-M-xuntuk "instrumen" itu. Kemudian evaluasi fungsi, misalnya dengan menempatkan titik setelah (triangle-using-cond 3)dan memukul C-x C-e.

Anda sekarang dalam mode Edebug. Tekan bilah spasi untuk melangkah melalui fungsi. Nilai menengah dari setiap ekspresi ditampilkan di area gema. Untuk keluar dari mode Edebug, tekan saja q. Untuk menghapus instrumentasi, beri titik di mana saja di dalam definisi dan tekan C-M-xuntuk mengevaluasi kembali definisi.

Menggunakan debugger Emacs standar

M-x debug-on-entry triangle-using-cond, kemudian, ketika triangle-using-conddipanggil, Anda ditempatkan di debugger Emacs (buffer *Backtrace*).

Langkah melalui evaluasi menggunakan d(atau cuntuk melewati evaluasi yang tidak menarik).

Untuk melihat kondisi antara (nilai variabel, dll.) Anda dapat menggunakan ekapan saja. Anda diminta memasukkan sexp untuk mengevaluasi, dan hasil evaluasi dicetak.

Saat Anda menggunakan debugger, buat salinan kode sumber terlihat di frame lain, sehingga Anda dapat mengikuti apa yang terjadi.

Anda juga dapat memasukkan panggilan eksplisit untuk memasukkan debugger (lebih atau kurang breakpoints) di tempat sewenang-wenang dalam kode sumber. Anda memasukkan (debug)atau (debug nil SOME-SEXP-TO-EVALUATE). Dalam kasus terakhir, ketika debugger dimasukkan SOME-SEXP-TO-EVALUATEdievaluasi dan hasilnya dicetak. (Ingatlah bahwa Anda dapat memasukkan kode seperti itu ke dalam kode sumber dan menggunakannya C-M-xuntuk mengevaluasinya, lalu batalkan - Anda tidak perlu menyimpan file yang diedit.)

Lihat manual Elisp, simpul Using Debuggeruntuk informasi lebih lanjut.

Rekursi sebagai lingkaran

Bagaimanapun, anggap rekursi sebagai satu lingkaran. Ada dua kasus terminasi yang didefinisikan: (<= number 0)dan (= number 1). Dalam kasus ini fungsi mengembalikan angka sederhana.

Dalam kasus rekursif fungsi mengembalikan jumlah dari angka itu dan hasil dari fungsi dengan number - 1. Akhirnya, fungsi akan dipanggil dengan salah satu 1atau nomor yang lebih kecil dari atau sama dengan nol.

Karenanya, hasil kasus rekursif adalah:

(+ number (+ (1- number) (+ (1- (1- number)) ... 1)

Ambil contoh (triangle-using-cond 4). Mari kita akumulasikan ekspresi terakhir:

• di iterasi pertama numberadalah 4, sehingga (> number 1)cabang diikuti. Kami mulai membangun ekspresi (+ 4 ...dan memanggil fungsi dengan (1- 4), yaitu (triangle-using-cond 3).

• sekarang numberadalah 3, dan hasilnya adalah (+ 3 (triangle-using-cond 2)). Ekspresi hasil total adalah (+ 4 (+ 3 (triangle-using-cond 2))).

• numberadalah 2sekarang, jadi ekspresi adalah(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))

• numberadalah 1sekarang, dan kita mengambil (= number 1)cabang, sehingga membosankan sebuah 1. Seluruh ekspresi itu (+ 4 (+ 3 (+ 2 1))). Evaluasi yang dari dalam ke luar dan Anda mendapatkan: (+ 4 (+ 3 3)), (+ 4 6), atau hanya 10.

Model Substitusi untuk Prosedur Aplikasi dari SICP dapat menjelaskan algoritma untuk memahami kode seperti ini.

Saya menulis beberapa kode untuk memfasilitasi ini juga. lispy-flattendari paket lispy melakukan ini. Inilah hasil melamar lispy-flattenke (triangle-using-cond 4):

(cond ((<= 4 0)
       0)
      ((= 4 1)
       1)
      ((> 4 1)
       (+ 4 (triangle-using-cond (1- 4)))))

Anda dapat menyederhanakan ungkapan di atas menjadi hanya:

(+ 4 (triangle-using-cond 3))

Kemudian ratakan sekali lagi:

(+ 4 (cond ((<= 3 0)
            0)
           ((= 3 1)
            1)
           ((> 3 1)
            (+ 3 (triangle-using-cond (1- 3))))))

Hasil akhir:

(+ 4 (+ 3 (+ 2 1)))

Ini tidak spesifik untuk Emacs / Elisp, tetapi jika Anda memiliki latar belakang matematika, maka rekursi seperti induksi matematika . (Atau jika Anda tidak: maka ketika Anda belajar induksi, itu seperti rekursi!)

Mari kita mulai dengan definisi:

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

Ketika numberini 4, tak satu pun dari dua kondisi pertama terus, jadi itu dievaluasi sesuai dengan kondisi ketiga:
(triangle-using-cond 4)dievaluasi sebagai
(+ number (triangle-using-cond (1- number))), yaitu sebagai
(+ 4 (triangle-using-cond 3)).

Demikian pula,
(triangle-using-cond 3)dievaluasi sebagai
(+ 3 (triangle-using-cond 2)).

Demikian pula, (triangle-using-cond 2)dievaluasi sebagai
(+ 2 (triangle-using-cond 1)).

Tetapi untuk (triangle-using-cond 1), kondisi kedua berlaku, dan itu dievaluasi sebagai 1.

Sepotong saran bagi siapa pun yang mempelajari rekursi: cobalah untuk menghindarinya

kesalahan pemula yang umum adalah mencoba memikirkan tentang apa yang terjadi selama panggilan rekursif alih-alih percaya bahwa panggilan rekursif bekerja (kadang-kadang disebut lompatan iman rekursif).

Jika Anda mencoba meyakinkan diri sendiri apakah (triangle-using-cond 4)akan mengembalikan jawaban yang benar, anggap saja itu (triangle-using-cond 3)akan mengembalikan jawaban yang benar, dan verifikasi apakah jawaban itu akan benar dalam kasus itu. Tentu saja Anda harus memverifikasi casing dasar juga.

Langkah-langkah perhitungan untuk contoh Anda akan seperti berikut:

(4 +               ;; step 1
   (3 +            ;; step 2
      (2 +         ;; step 3
         (1))))    ;; step 4
=> 10

Kondisi 0 sebenarnya tidak pernah dipenuhi karena 1 sebagai input sudah mengakhiri rekursi.

Saya pikir itu cukup mudah, Anda tidak perlu emacs lisp di bawah ini, itu hanya matematika sekolah dasar.

f (0) = 0

f (1) = 1

f (n) = f (n-1) + n saat n> 1

jadi f (5) = 5 + f (4) = 5 + 4 + f (3) = 5 + 4 + 3 + 2 + 1 + 0

Sekarang sudah jelas.