Memahami Rekursi dalam Python: Jadi, adakah anda akan menghadapinya?

Rekursi ialah konsep asas dalam pengaturcaraan, tetapi kadangkala ia kelihatan agak misteri. Jadi, mari kita permudahkan perkara ini dan lihat bahawa ia lebih mudah daripada yang kelihatan!

Apakah Rekursi?

Rekursi ialah apabila fungsi menyelesaikan masalah dengan memanggil... sendiri! Ya, betul. Ia berfungsi seperti cerita yang anda ceritakan berulang kali, hanya pendek sedikit setiap kali sehingga anda sampai ke penghujungnya. Tetapi untuk ia berfungsi dengan baik, ia perlu memenuhi dua peraturan emas:

1. Syarat Penamatan: ia adalah titik di mana fungsi mesti berhenti, jika tidak, ia akan kekal dalam gelung kekal (kita tidak mahu itu, kan?).
2. Panggilan kendiri: ini adalah apabila fungsi memanggil dirinya sendiri, semakin dalam dan dalam sehingga mencapai keadaan penamatan.

Sekarang, mari lihat cara ini berfungsi dalam amalan!

Bagaimana ia berfungsi?

Untuk menerangkannya dengan lebih baik, tiada yang lebih baik daripada contoh klasik faktorial! Bayangkan kita mahu mengira (5!) (baca "lima faktorial"). Bagaimana ia berfungsi?

5! = 5 * 4 * 3 * 2 * 1!

Namun, dengan rekursi, kita boleh memikirkannya seperti ini:

5! = 5 * 4!

Dan, dalam urutan, 4! ialah (4 * 3!), dan seterusnya, sehingga kita mencapai (1!), iaitu kes asas kami (penamatan keadaan).

Contoh Praktikal: Faktorial

Mari kita ke kod, kerana di situlah konsep itu dihidupkan! Berikut ialah pengiraan faktorial yang terkenal menggunakan rekursi:

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

Penjelasan:

1. Kes asas di sini ialah apabila nombor adalah 0 atau 1, di mana fungsi hanya mengembalikan 1.
2. Jika nombor lebih besar daripada 1, fungsi dipanggil dengan nombor - 1, mengumpul nilai sehingga huruf besar.

Kerumitan

• Masa: (O(n)) — kerana terdapat n panggilan rekursif.
• Ruang: (O(n)) — kedalaman tindanan pelaksanaan ialah n.

Contoh Praktikal: Fibonacci

Satu lagi contoh yang digunakan secara meluas ialah jujukan Fibonacci. Dia begini:

f(0) = 0, f(1) = 1, f(n) = f(n - 1) f(n - 2)

Mari kita ke kod!

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

Kerumitan Fibonacci:

• Masa: (O(2^n)) — eksponen! ⚠️
• Ruang: (O(n)) — penggunaan tindanan untuk panggilan rekursif.

Itulah sebabnya, untuk nilai yang besar, pengiraan Fibonacci dengan rekursi tulen boleh menjadi agak menyusahkan. Tetapi untuk tujuan pembelajaran, ia adalah contoh yang bagus!

Akhirnya

Rekursi ialah konsep utama dalam pengaturcaraan dan, walaupun ia kelihatan agak menakutkan pada mulanya, ia menjadi lebih mudah dengan latihan. Contoh faktorial dan Fibonacci ini hanyalah permulaan!

Jika anda ingin berlatih, lihat dan buat salinan, dalam Colab ini di sini!

Atas ialah kandungan terperinci Memahami Rekursi dalam Python: Jadi, adakah anda akan menghadapinya?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!