Algoritma rekursif [menghitung faktorial]

Algoritma Rekursif [Menghitung Faktorial]

2024-07-12

algoritma rekursifadalah teknik pemrograman yang banyak digunakan dalam ilmu komputer dan matematika yang memungkinkan fungsilangsungatautidak langsungtanahmemanggil dirinya sendiri untuk memecahkan masalah.rekursifIde dasarIni adalah penguraian masalah-masalah kompleks menjadi sub-masalah yang lebih kecil dan serupa hingga sub-masalah tersebut cukup sederhana untuk diselesaikan secara langsung.

Algoritma rekursif biasanya berisi dua bagian utama:

Kasus Dasar: Ini adalah kondisi penghentian panggilan rekursif, yaitu contoh masalah paling sederhana yang dapat dijawab secara langsung tanpa panggilan rekursif lebih lanjut.
Kasus Rekursif: Ini adalah proses memecah masalah menjadi submasalah yang lebih kecil dan menyelesaikan submasalah tersebut melalui panggilan rekursif. Kasus rekursif harus memastikan bahwa setiap panggilan maju menuju kasus dasar.

Langkah-langkah algoritma rekursif:

Identifikasi kasus dasar: Tentukan masalah mana yang dapat diselesaikan secara langsung tanpa panggilan rekursif lebih lanjut.
Rancang situasi rekursi: Tentukan cara memecah masalah besar menjadi sub-masalah yang lebih kecil dan cara menggabungkan solusi dari sub-masalah tersebut untuk mendapatkan solusi terhadap masalah awal.
Menjamin konvergensi rekursif: Pastikan panggilan rekursif pada akhirnya mencapai kasus dasar dan menghindari rekursi tak terbatas.

Kelebihan dan kekurangan algoritma rekursif:

keuntungan: Kodenya ringkas, logikanya jelas, dan mudah dipahami serta ditulis.
kekurangan : Mungkin kurang efisien dibandingkan solusi berulang karena melibatkan lebih banyak overhead pemanggilan fungsi. Selain itu, rekursi yang terlalu dalam dapat menyebabkan kesalahan stack overflow.

Rekursi memiliki aplikasi dalam banyak algoritma, sepertipenjelajahan pohon、Pencarian grafik、Pemrograman dinamis, dll. . Penggunaan rekursi yang tepat dapat menyederhanakan penyelesaian masalah yang kompleks.

Contoh: Menghitung faktorial

def factorial(n):#自定义求n的阶乘函数
        if n==1:#判断n=1
                return 1#返回1结束
        else:#递归条件 即n!=1
                return n*factorial(n-1)#递归求阶乘

number = int(input("请输入一个正整数:"))#输入n的值
result = factorial(number)#调用阶乘函数
print("%d 的阶乘是 %d" %(number,result))#输出结果
1
2
3
4
5
6
7
8
9

Masukkan deskripsi gambar di sini

Penjelasan kode

factorial Fungsi tersebut menerima parameter n , mewakili bilangan yang faktorialnya akan dihitung.Faktorialnya dinyatakan sebagain!, didefinisikan sebagai semua kurang dari atau sama dengan n Hasil kali bilangan bulat positif. Misalnya,5! = 5 × 4 × 3 × 2 × 1 = 120。

Di dalam fungsinya:

Kasus dasar: jika n Jika sama dengan 1, fungsi mengembalikan 1 secara langsung. Ini adalah kondisi terminasi rekursi karena faktorial dari 1 didefinisikan sebagai 1.
Kasus rekursif: jika n tidak sama dengan 1, fungsinya akann Danfactorial(n-1) Hasilnya berlipat ganda.factorial(n-1) adalah benarfactorial fungsiPanggilan itu sendiri , tetapi parameternya dikurangi 1.Panggilan ini akan berlanjut sampain mencapai 1.

Kunci dari rekursi adalah setiap panggilan rekursif bergerak mendekati kasus dasar, akhirnya mencapai kasus dasar dan mulai mengembalikan nilai. Dalam contoh ini, setiap panggilan rekursif mengurangi n sebanyak 1 hingga n menjadi 1.

Melihat:

Rekursi mungkin mengalami masalah kinerja atau kesalahan stack overflow saat menangani nilai besar karena setiap pemanggilan fungsi menghabiskan sebagian ruang tumpukan. Untuk operasi matematika sederhana seperti faktorial, seringkali terdapat metode iteratif yang lebih efisien dan ramah memori. Namun, rekursi memberikan cara yang elegan dan mudah dipahami untuk menyelesaikan masalah tertentu.

Berbagi teknologi