PHP Master | Memahami rekursi

mata teras

rekursi adalah kaedah penyelesaian masalah yang melibatkan fungsi yang memanggilnya secara langsung atau tidak langsung (melalui gelung panggilan fungsi). Ia amat berguna apabila ia meleleh melalui pokok dan senarai atau melakukan kebanyakan o (n log n) macam.
Fungsi rekursif mesti mempunyai klausa asas atau klausa perlindungan untuk menghalang mereka daripada memanggil diri mereka tanpa batas, mengakibatkan ralat limpahan stack. Contoh asas ini adalah syarat yang menghentikan fungsi daripada membuat panggilan rekursif selanjutnya apabila keadaan tertentu dipenuhi.
Terdapat dua jenis rekursi: rekursi langsung dan rekursi tidak langsung. Rekursi langsung bermaksud bahawa fungsi itu memanggil secara langsung, sementara rekursi tidak langsung bermaksud bahawa fungsi secara tidak langsung memanggil dirinya melalui fungsi lain. Artikel ini memberi tumpuan kepada rekursi langsung.
Walaupun rekursi boleh menjadi alat yang berkuasa, ia mesti digunakan dengan berhati -hati. PHP tidak mengoptimumkan fungsi rekursif, dan mereka biasanya tidak cekap dan cepat sebagai rakan -rakan iteratif mereka. Walau bagaimanapun, rekursi mungkin lebih cekap dalam beberapa kes, seperti mencari atau melintasi kedalaman yang tidak menentu dalam sistem fail.

Dalam jawatan terdahulu saya menulis tentang pengaliran dan cara menggunakannya. Hari ini, saya mahu melihat adik berulang: rekursi. Walau bagaimanapun, sebelum kita membincangkan rekursi, mari kita lihat kod ini:

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

Kilang adalah hasil daripada nombor yang didarabkan oleh semua integer positif yang lebih kecil daripada nombor tersebut. Sekarang mari kita menulis semula contoh ini seperti ini:

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Apabila kita memanggil kedua -dua fungsi ini, kita mendapat hasil yang sama, tetapi perhatikan bahawa fungsi kedua mengira faktorial dengan memanggil sendiri. Ini dipanggil rekursi.

Apa itu rekursi?

Fungsi rekursif merujuk kepada fungsi yang memanggil diri mereka secara langsung atau melalui gelung panggilan fungsi. Rekursi juga boleh merujuk kepada kaedah penyelesaian masalah yang pertama menyelesaikan versi masalah yang lebih kecil dan kemudian menggunakan hasilnya untuk menambah beberapa pengiraan lain untuk membentuk jawapan kepada soalan asal. Biasanya, dalam proses menyelesaikan versi yang lebih kecil, pendekatan ini akan menyelesaikan versi teka-teki yang lebih kecil, dan sebagainya, sehingga "contoh asas" yang mudah dicapai. Untuk menulis fungsi rekursif, anda perlu menyediakannya dengan beberapa kaedah pulangan, jika tidak, ia akan terus memanggil dirinya selama -lamanya (atau sehingga tumpukan panggilan pecah, skrip tamat, atau memori habis). Ini dipanggil klausa perlindungan atau kes asas. Bentuk paling mudah fungsi rekursif adalah seperti berikut:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Jenis rekursif

Apabila fungsi memanggil secara langsung, ia dipanggil rekursi langsung. Panggilan akhir fungsi kepada dirinya sendiri dalam gelung panggilan fungsi dipanggil rekursi tidak langsung. Sila lihat contoh berikut rekursi tidak langsung:

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

<code>Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0</code>

Contoh di atas sebenarnya adalah kod yang tidak berguna, hanya untuk menunjukkan kepada anda bagaimana fungsi memanggil secara tidak langsung melalui fungsi lain. Memanggil A (N & Gt; 4) atau B (N & Gt; 4) menyebabkan fungsi yang dipanggil dari panggilan fungsi lain. Adalah penting untuk mengetahui bahawa fungsi boleh memanggil diri mereka secara tidak langsung seperti ini, tetapi dalam artikel ini kita hanya berurusan dengan rekursi langsung.

Contoh praktikal

Untuk menunjukkan kepada anda kuasa rekursi, kami akan menulis fungsi yang mencari kunci dalam array dan mengembalikan hasilnya.

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

semuanya berjalan lancar, tetapi ambil perhatian bahawa kami hanya berulang ke lapisan kedua array, jadi mencari "Fibonacci" di lapisan ketiga gagal. Sekiranya kita mencari tatasusunan kedalaman yang tidak menentu, ini tidak akan mencukupi. Kita boleh menulis semula carian sebagai fungsi rekursif:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Menggunakan fungsi rekursif, kita boleh mencari beberapa lapisan tatasusunan yang mendalam kerana kita tidak mempunyai kedalaman fungsi keras. Ia hanya terus berjalan sehingga berulang melalui semua nilai dalam array.

rekursi kepala dan rekursi ekor

Dalam semua contoh kami setakat ini, kami telah menggunakan rekursi header yang dipanggil. Apabila fungsi memanggil sendiri, ia menunggu hasil dari panggilan sebelum mengembalikan nilai sendiri. Anda boleh menulis fungsi yang tidak beroperasi pada nilai pulangan, tetapi melepasi semua nilai yang diperlukan sebagai parameter. Ini dipanggil panggilan ekor (atau rekursi ekor). Kaedah ini biasanya lebih disukai kerana runtime bahasa kadang -kadang boleh mengoptimumkan panggilan, jadi tidak ada bahaya untuk meletupkan tumpukan panggilan, tetapi PHP tidak berbuat demikian. Berikut adalah contoh faktorial kami, diubahsuai untuk membuat panggilan ekor. Perhatikan bahawa hasil panggilan rekursif dikembalikan, bukannya memanipulasi lagi.

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

Cadangan Umum

Mana -mana kod yang boleh ditulis secara berulang boleh ditulis secara rekursif. Walau bagaimanapun, ini tidak selalu mudah dilakukan (walaupun bijak). Rekursi adalah sangat baik apabila ia melangkah melalui pokok dan senarai atau melakukan kebanyakan o (n log n) macam. Rekursi lebih sesuai daripada kaedah berulang apabila anda perlu membahagikan masalah berulang, seperti mencari dalam sistem fail, dan anda juga perlu pergi ke mana -mana subdirektori untuk mencari. Rekursi berfungsi dengan baik apabila melintasi kedalaman yang tidak menentu. Ingat bahawa PHP tidak mengoptimumkan fungsi rekursif, dan walaupun anda menulisnya untuk panggilan ekor, fungsi rekursif biasanya tidak cekap dan lebih perlahan daripada rakan -rakan berulang mereka, walaupun kadang -kadang mereka melakukan pekerjaan yang lebih baik, seperti dalam contoh kod di atas yang ditunjukkan. Rekursi biasanya merupakan alternatif pilihan untuk lelaran dalam pengaturcaraan berfungsi, jadi kebanyakan bahasa berfungsi mengoptimumkan fungsi rekursif. Jika anda menggunakan XDebug, pastikan anda menyemak konfigurasi sistem anda. Secara lalai, anda akan mengehadkan 100 panggilan rekursif, dan jika anda melebihi had ini, skrip anda akan membuang "had bersarang maksimum telah dicapai" ralat. Jika anda perlu menukar tetapan ini, anda boleh mengemas kini nilai konfigurasi debug.max_nesting_level. Akhirnya, lebih baik membaca penjelasan timbunan timbunan dan rekursi yang menyebabkan limpahan timbunan untuk memahami apa yang berlaku untuk memanggil timbunan semasa rekursi.

Kesimpulan

Dalam artikel ini, saya memperkenalkan anda secara meluas kepada rekursi dan perbandingannya dengan lelaran. Saya juga menunjukkan kepada anda cara menulis fungsi rekursif, bila menulisnya, dan mengapa. Saya juga cuba memberi amaran kepada anda tentang beberapa perangkap yang mungkin anda hadapi ketika menggunakan rekursi. Rekursi adalah seperti ini, bahkan banyak pengaturcara yang berpengalaman mungkin tidak menggunakannya selama bertahun -tahun, dan banyak lagi yang tidak pernah mendengarnya, yang memalukan kerana ia adalah konsep yang benar -benar kuat. Saya berharap bahawa melalui jawatan ini saya dapat memberi anda pengetahuan yang cukup untuk mula menulis fungsi rekursif anda sendiri. Tetapi ingat bahawa seperti menggunakan api, anda mesti sentiasa menggunakan alat ini dengan berhati -hati.

gambar dari Alexandre Duret-Lutz oleh Flickr

FAQs on Defreated Recursion in PHP (FAQ)

Apakah contoh asas dalam fungsi rekursif PHP?

Contoh asas dalam fungsi rekursif PHP adalah syarat yang menghalang fungsi dari memanggil dirinya tak terhingga. Ia adalah bahagian utama dari sebarang fungsi rekursif. Tanpa kes asas, fungsi rekursif akan memanggil dirinya tak terhingga, mengakibatkan ralat limpahan timbunan. Dalam PHP, contoh asas biasanya ditakrifkan menggunakan pernyataan "jika" pada permulaan fungsi. Fungsi memeriksa syarat ini sebelum meneruskan dengan panggilan rekursif. Sekiranya keadaan dipenuhi, fungsi itu mengembalikan nilai dan berhenti memanggilnya sendiri.

Bagaimana fungsi rekursif dalam kerja PHP?

Fungsi rekursif dalam PHP memanggil dirinya dalam badan fungsi sendiri sehingga keadaan tertentu dipanggil kes asas dipenuhi. Apabila fungsi rekursif dipanggil, ia melakukan tugas tertentu dan kemudian memanggil dirinya untuk mengulangi tugas. Proses ini berterusan sehingga kes asas dipenuhi, dan fungsi berhenti memanggilnya sendiri. Setiap kali fungsi dipanggil, lapisan baru dicipta pada timbunan panggilan, menyimpan pembolehubah dan alamat pulangan panggilan fungsi. Sebaik sahaja kes asas dipenuhi, fungsi mula kembali dan melepaskan lapisan stack panggilan oleh lapisan.

Bolehkah semua masalah dalam PHP diselesaikan menggunakan rekursi?

Walaupun rekursi boleh menjadi alat yang berkuasa dalam PHP, tidak semua masalah boleh atau harus diselesaikan menggunakan rekursi. Rekursi paling sesuai untuk masalah yang boleh dipecah menjadi masalah yang lebih kecil, lebih serupa, seperti melintasi direktori fail atau susunan penyortiran. Walau bagaimanapun, jika digunakan secara tidak wajar, rekursi boleh menyebabkan penggunaan memori yang tinggi dan kesilapan melimpah. Ia juga biasanya lebih perlahan daripada penyelesaian berulang kerana overhead panggilan fungsi. Oleh itu, sangat penting untuk memahami masalah di tangan dan memilih pendekatan yang betul.

Bagaimana untuk mengelakkan limpahan timbunan dalam fungsi rekursif PHP?

Stack Overflow dalam fungsi rekursif boleh dicegah dengan berhati -hati menentukan contoh asas bahawa fungsi akhirnya akan dicapai. Kes asas adalah syarat, dan apabila keadaan ini dipenuhi, fungsi berhenti membuat panggilan rekursif selanjutnya. Tanpa kes asas, fungsi itu akan memanggil dirinya secara tak terhingga, menyebabkan limpahan timbunan. Ia juga penting untuk memastikan bahawa setiap panggilan rekursif membawa fungsi lebih dekat kepada kes asas untuk mengelakkan rekursi tak terhingga.

Apakah rekursi ekor dalam php?

rekursi ekor adalah jenis rekursi khas, di mana panggilan rekursif adalah operasi terakhir dalam fungsi. Ini bermakna tidak perlu menjejaki panggilan fungsi terdahulu, yang membolehkan pengkompil atau penterjemah mengoptimumkan rekursi dan mengurangkan risiko limpahan timbunan. Walau bagaimanapun, PHP sendiri tidak menyokong pengoptimuman rekursif ekor. Oleh itu, semasa anda boleh menulis fungsi rekursif ekor di PHP, mereka tidak dioptimumkan dan masih akan menggunakan ruang stack untuk setiap panggilan rekursif.

Bagaimana membandingkan rekursi dengan gelung dalam php?

Kedua -dua rekursi dan gelung boleh digunakan untuk mengulangi satu set arahan dalam PHP. Walau bagaimanapun, mereka bekerja secara berbeza dan mempunyai kelebihan dan kekurangan yang berbeza. Rekursi adalah alat yang berkuasa untuk menyelesaikan masalah yang kompleks yang boleh dipecah menjadi masalah yang lebih kecil dan lebih serupa. Ia amat berguna untuk melintasi tugas -tugas seperti pokok atau graf. Gelung, sebaliknya, sering lebih sesuai untuk tugas berulang -ulang. Mereka menggunakan memori yang kurang daripada rekursi dan tidak mungkin menyebabkan limpahan timbunan.

Bolehkah saya menggunakan rekursi untuk melangkah ke atas tatasusunan dalam php?

Ya, rekursi boleh menjadi cara yang sangat berkesan untuk melintasi tatasusunan (terutamanya array multidimensi) dalam PHP. Anda boleh menggunakan fungsi rekursif untuk melangkah ke atas setiap elemen dalam array, dan jika elemen itu sendiri adalah array, fungsi itu boleh memanggil dirinya untuk berulang di atas array. Proses ini berterusan sehingga semua elemen diakses. Walau bagaimanapun, ingat bahawa rekursi mungkin lebih perlahan daripada penyelesaian berulang dan akan menggunakan lebih banyak ingatan, terutamanya dalam kes tatasusunan besar.

Apakah rekursi bersama dalam PHP?

rekursi bersama merujuk kepada dua atau lebih fungsi yang dipanggil antara satu sama lain dalam gelung. Dalam PHP, ini bermakna fungsi fungsi panggilan B, dan fungsi B panggilan fungsi A. Ini boleh menjadi alat yang berkuasa untuk menyelesaikan jenis masalah tertentu, tetapi ia juga boleh menjadi lebih sukar untuk difahami dan debug daripada rekursi mudah. Seperti mana -mana fungsi rekursif, adalah penting untuk menentukan kes asas untuk mencegah rekursi tak terhingga.

Bagaimana cara debug fungsi rekursif dalam php?

Debugging fungsi rekursif dalam PHP boleh mencabar kerana fungsi itu memanggil sendiri beberapa kali. Walau bagaimanapun, terdapat beberapa strategi yang boleh anda gunakan. Salah satu cara ialah menggunakan pernyataan cetak atau debugger untuk mengesan panggilan fungsi dan melihat status pembolehubah dalam setiap langkah. Cara lain ialah menarik pokok rekursif untuk menggambarkan panggilan fungsi. Ia juga penting untuk menyemak semula kes asas dan kes rekursi untuk memastikan ia betul.

Apakah batasan menggunakan rekursi dalam PHP?

Walaupun rekursi boleh menjadi alat yang berkuasa di PHP, ia mempunyai beberapa batasan. Salah satu batasan utama ialah jika rekursi terlalu mendalam, terdapat risiko limpahan timbunan. Ini kerana setiap panggilan rekursif menambah lapisan baru ke timbunan panggilan dan saiz timbunan terhad. Oleh kerana overhead panggilan fungsi, rekursi juga mungkin lebih perlahan daripada penyelesaian berulang dan akan menggunakan lebih banyak ingatan. Selain itu, fungsi rekursif mungkin lebih sukar untuk difahami dan debug daripada penyelesaian berulang.

Atas ialah kandungan terperinci PHP Master | Memahami rekursi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!