Orang yang memiliki pengalaman dalam pemrograman pasti sudah familiar dengan fungsi rekursif. Kita sering menggunakan rekursi untuk menyelesaikan serangkaian masalah yang kompleks. Algoritma rekursif sangat efektif untuk sebagian besar masalah, dan mereka juga dapat mengoptimalkan kode kita. Ada beberapa hal yang perlu diperhatikan saat menggunakan rekursi:
1) Rekursi memanggil fungsi itu sendiri di dalam fungsi itu sendiri.
2) Efisiensi rekursi relatif rendah, dan tidak disarankan menggunakannya jika ada batasan waktu.
3) Perlu adanya kondisi akhir yang jelas dalam proses rekursif, yaitu jalan keluar rekursif.
Mari kita jelaskan fungsi rekursif secara detail di bawah ini.
Pertama mari kita lihat penggunaan sederhana rekursi melalui sebuah contoh:
m=int(input('Masukkan angka:'))deftest(x):x+=2ifx<100:test(x)else:print('X terakhir adalah:',x)test(m)
Outputnya adalah:
Masukkan angka: 20 dan x terakhir adalah: 100
Mari kita analisis contoh ini. Pertama, pada baris kode pertama, kita memasukkan bilangan bulat. Pada baris terakhir, m diteruskan sebagai parameter aktual ke metode test() 2 terlebih dahulu, lalu penilaian, jika nilai x kurang dari 100, panggil kembali fungsi ini saat memanggil, nilai x saat ini digunakan sebagai parameter aktual untuk berpartisipasi dalam panggilan =100 puas.
Lihatlah diagram di bawah ini:
Artinya, jika kondisi tidak terpenuhi, ia akan kembali ke lapisan terluar dan memanggil fungsi ini.
Jika berbicara tentang masalah klasik pada algoritma rekursif, deret Fibonacci dan Tower of Hanoi selalu tidak dapat dipisahkan. Disini kami akan menjelaskan cara menggunakan rekursi untuk menyelesaikan deret Fibonacci.
Pertama-tama perlu kita ketahui bahwa rumus rekursif barisan Fibonacci adalah F(n)=F(n-1)+F(n-2), F(1), dan F(2) adalah 1. Kita dapat menggunakan rekursi Untuk mencari nilai suatu item dalam deret Fibonacci.
Ada banyak cara yang bisa kita gunakan untuk menyelesaikan soal deret Fibonacci.
Pertama kita menggunakan metode rekursif yang umum digunakan untuk menyelesaikan masalah ini:
N=int(input(masukkan jumlah item yang ingin diperoleh:))deffibonacci(n):ifn<=2:#Jika kurang dari atau sama dengan 2, set n ke 1 return1else:returnfibonacci(n-1) +fibonacci(n-2)print ('Nilai yang sesuai adalah',fibonacci(n))
Outputnya adalah:
Masukkan jumlah item yang ingin Anda dapatkan: 4 sama dengan 3
Untuk metode pemanggilan rekursif ini, ketika kita memasukkan nilai 4, operasi berikut akan dilakukan secara rekursif:
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2)
Maka kita dapat melihat bahwa nilai suku keempat adalah 1+1+1=3.
Faktanya, metode penyelesaian ini hanya membuang-buang waktu karena diperlukan terlalu banyak iterasi. Kita juga dapat menggunakan ruang daripada waktu untuk menyelesaikan masalah ini.
Kodenya adalah sebagai berikut:
n=int(input(masukkan banyaknya suku yang ingin diperoleh :))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print (' Nilai yang sesuai adalah',fibonacci[n-1])
Outputnya adalah:
Masukkan jumlah item yang ingin Anda dapatkan: 4 sama dengan 3
Dengan cara ini, pertama-tama kita tentukan nilai dari dua item pertama dalam daftar, dan kemudian untuk jumlah n item yang ingin kita selesaikan, kita langsung mengisi daftar angka Fibonacci ke item yang kita perlukan melalui rumus, dan terakhir menurut indeks Nilainya langsung menemukan hasil keluaran yang sesuai.
Itu saja untuk fungsi rekursif. Seperti disebutkan di atas, kita harus memberikan perhatian khusus pada pintu keluar rekursif dan batas waktu. Pintu keluar adalah kunci akhir dari rekursi melebihi waktu yang ditentukan, saat ini kita perlu mengubah pemikiran kita untuk menyelesaikan masalah tersebut.