Operasi rekursif dalam pembangunan perisian

Mari kita lihat faktorial rekursif klasik ini:

#include
int factorial(int n)
{
int previous = 0xdeadbeef;
if (n == 0 || n == 1) {
return 1;
}
previous = factorial(n-1);
return n * previous;
}
int main(int argc)
{
int answer = factorial(5);
printf("%d\n", answer);
}

Rekursif faktorial - faktorial.c
Idea fungsi memanggil dirinya sendiri adalah sukar untuk difahami pada mulanya. Untuk menjadikan proses ini lebih jelas dan konkrit, rajah berikut menunjukkan titik akhir pada tindanan apabila faktorial(5) dipanggil dan baris kod n == 1 dicapai:

Setiap kali faktorial dipanggil, bingkai tindanan baharu dijana. Penciptaan dan pemusnahan bingkai tindanan ini adalah yang menjadikan versi rekursif secara faktorial lebih perlahan daripada versi berulangnya yang sepadan. Pengumpulan bingkai tindanan ini mungkin menghabiskan ruang tindanan sebelum panggilan kembali, menyebabkan program anda ranap.

Dan kebimbangan ini selalunya wujud secara teori. Sebagai contoh, bingkai tindanan mengambil 16 bait untuk setiap faktorial (ini mungkin bergantung pada susunan tindanan dan faktor lain). Jika anda menjalankan kernel Linux x86 moden pada komputer anda, anda biasanya mempunyai 8 GB ruang tindanan, jadi n dalam program faktorial boleh meningkat kepada kira-kira 512,000. Ini adalah hasil yang besar, dan memerlukan 8,971,833 bit untuk mewakilinya, jadi ruang tindanan tidak menjadi masalah sama sekali: integer kecil—walaupun integer 64-bit—disimpan dalam ruang tindanan kami Ia telah melimpah ribuan kali sebelum ini dah habis.

Kita akan melihat penggunaan CPU sebentar lagi, mari kita berundur dari bit dan bait dan menganggap rekursi sebagai teknologi umum. Algoritma faktorial kami bermula dengan menolak integer N, N-1, … 1 ke dalam tindanan dan mendarabkannya dalam susunan terbalik. Kami sebenarnya menggunakan timbunan panggilan program untuk mencapai ini, berikut ialah butirannya: kami memperuntukkan timbunan pada timbunan dan menggunakannya. Walaupun timbunan panggilan mempunyai ciri khas, ia hanyalah satu lagi struktur data yang boleh anda gunakan walau bagaimanapun anda mahu. Saya harap rajah ini membantu anda memahami perkara ini.

Apabila anda menganggap tindanan panggilan sebagai struktur data, sesuatu menjadi lebih jelas: menimbun integer tersebut dan kemudian mendarabkannya bukanlah idea yang baik. Itulah pelaksanaan yang cacat: ia seperti mengambil pemutar skru untuk memacu paku. Adalah lebih munasabah untuk menggunakan proses berulang untuk mengira faktorial.

Namun begitu, terdapat banyak skru sehinggakan kita hanya boleh memilih satu sahaja. Terdapat soalan wawancara klasik di mana terdapat tetikus dalam labirin dan anda perlu membantu tetikus mencari sekeping keju. Katakan seekor tikus boleh membelok ke kiri atau kanan dalam labirin. Bagaimanakah anda membuat model untuk menyelesaikan masalah ini?

Seperti banyak masalah dalam kehidupan sebenar, anda boleh memudahkan masalah tikus mencari keju ini menjadi graf, dengan setiap nod pokok binari mewakili kedudukan dalam mez. Anda kemudiannya boleh menyuruh tetikus membelok ke kiri di mana mungkin, dan apabila ia mencapai jalan buntu, mundur dan belok kanan semula. Ini ialah contoh tetikus berjalan melalui labirin:

Setiap kali sampai ke tepi (garisan), biarkan tetikus membelok ke kiri atau kanan untuk mencapai kedudukan baharu. Jika anda disekat ke mana-mana arah yang anda pusing, ini bermakna kelebihan yang berkaitan tidak wujud. Sekarang, mari kita bincangkannya! Proses ini, sama ada anda menggunakan timbunan panggilan atau struktur data lain, tidak dapat dipisahkan daripada proses rekursif. Dan menggunakan timbunan panggilan adalah sangat mudah:

#include
#include "maze.h"
int explore(maze_t *node)
{
int found = 0;
if (node == NULL)
{
return 0;
}
if (node->hasCheese){
return 1;// found cheese
}
found = explore(node->left) || explore(node->right);
return found;
}
int main(int argc)
{
int found = explore(&maze);
}

Muat Turun Penyelesaian Maze Rekursif
Apabila kita menemui keju dalam maze.c:13, susunannya kelihatan seperti ini. Anda juga boleh melihat data yang lebih terperinci dalam output GDB, iaitu data yang dikumpul menggunakan arahan.

Ia menunjukkan tingkah laku rekursi yang baik, kerana ini adalah masalah yang sesuai untuk menggunakan rekursi. Dan ia tidak menghairankan: apabila ia datang kepada algoritma, rekursi adalah peraturan, bukan pengecualian. Ia muncul apabila anda mencari, apabila anda melintasi pepohon dan struktur data lain, apabila anda menghuraikan, apabila anda perlu mengisih -- ia ada di mana-mana. Sama seperti pi atau e dikenali sebagai "tuhan" dalam matematik kerana ia adalah asas kepada segala-galanya di alam semesta, rekursi adalah sama: ia hanya wujud dalam struktur pengiraan.

Keindahan buku Steven Skienna yang sangat baik, A Guide to Algorithm Design ialah dia menerangkan kerjanya melalui "kisah perang" sebagai cara untuk menunjukkan algoritma di sebalik penyelesaian masalah dunia sebenar. Ini adalah sumber terbaik yang saya tahu untuk mengembangkan pengetahuan anda tentang algoritma. Bacaan lain ialah kertas asal McCarthy mengenai pelaksanaan LISP. Rekursi ialah nama dan prinsip asasnya dalam bahasa. Kertas kerja ini boleh dibaca dan menarik, dan ia adalah menarik untuk melihat kerja sarjana di tempat kerja.

Berbalik kepada masalah maze. Walaupun sukar untuk meninggalkan rekursi di sini, ini tidak bermakna ia mesti dicapai melalui timbunan panggilan. Anda boleh menggunakan rentetan seperti RRLL untuk menjejak belokan, dan kemudian gunakan rentetan ini untuk menentukan langkah seterusnya tetikus. Atau anda boleh menetapkan sesuatu yang lain untuk merekodkan keseluruhan status pencarian keju. Anda masih melaksanakan proses rekursif, anda hanya perlu melaksanakan struktur data anda sendiri.

Nampaknya lebih rumit kerana panggilan tindanan adalah lebih sesuai. Setiap bingkai tindanan merekodkan bukan sahaja nod semasa, tetapi juga keadaan pengiraan pada nod tersebut (dalam kes ini, sama ada kita hanya membiarkannya pergi ke kiri, atau telah cuba pergi ke kanan). Oleh itu, kod itu menjadi tidak penting. Walau bagaimanapun, kadangkala kami meninggalkan algoritma yang sangat baik ini kerana takut limpahan dan prestasi yang dijangkakan. Itu bodoh!

Seperti yang kita lihat, ruang tindanan adalah sangat besar, dan batasan lain sering ditemui sebelum ruang tindanan habis. Di satu pihak, anda boleh menyemak saiz masalah untuk memastikan ia boleh dikendalikan dengan selamat. Kebimbangan CPU didorong oleh dua contoh bermasalah yang diedarkan secara meluas: faktorial bodoh dan rekursi Fibonacci O(2n) tanpa ingatan yang mengerikan. Ia bukan perwakilan yang betul bagi algoritma rekursif tindanan.

Malah operasi tindanan adalah sangat pantas. Biasanya, timbunan mengimbangi kepada data adalah sangat tepat, ia adalah data panas dalam cache, dan arahan khusus beroperasi padanya. Pada masa yang sama, overhed yang dikaitkan dengan menggunakan struktur data anda sendiri yang diperuntukkan pada timbunan adalah penting. Ia sering dilihat bahawa orang menulis kaedah pelaksanaan yang lebih kompleks dan mempunyai prestasi yang lebih buruk daripada rekursi panggilan tindanan. Akhir sekali, prestasi CPU moden adalah sangat baik, dan secara amnya CPU tidak akan menjadi hambatan prestasi. Berhati-hati apabila mempertimbangkan untuk mengorbankan kesederhanaan program, sama seperti anda sentiasa mempertimbangkan prestasi program dan pengukuran prestasi itu.

Artikel seterusnya akan menjadi yang terakhir dalam siri Exploring Stack Kami akan mempelajari tentang panggilan ekor, penutupan dan konsep lain yang berkaitan. Kemudian, tiba masanya untuk menyelami rakan lama kita, kernel Linux. Terima kasih kerana membaca!

Atas ialah kandungan terperinci Operasi rekursif dalam pembangunan perisian. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!