Demystifying Python Recursion

Indonesian (Bahasa Indonesia) translation by Febri Ardian Sanjoyo (you can also view the original English article)

Sebagian besar tugas rumit dalam Python dapat dipecah menjadi subtugas sederhana. Rekursi membantu untuk mencapai ini, sehingga membuat kode bersih dan rapi. Tutorial ini akan memperkenalkan rekursi, manfaat rekursi, dan bagaimana menggunakannya dalam pemrograman Python.

Apa itu Rekursi?

Rekursi adalah metode pemecahan masalah dengan solusi untuk kasus yang lebih kecil dari masalah yang sama. Pendekatan ini dapat diterapkan untuk banyak jenis tantangan dalam pemrograman.

Manfaat Menggunakan Rekursi

Beberapa manfaat menggunakan rekursi adalah:

Rekursi menambah kesederhanaan saat menulis kode, sehingga lebih mudah didebug.
Rekursi mengurangi jumlah waktu yang dibutuhkan oleh suatu algoritma untuk berjalan sebagai fungsi dari input panjang.
Rekursi juga lebih disukai ketika memecahkan masalah yang sangat kompleks, terutama masalah pada struktur berbasis tree, karena kinerjanya lebih baik.

Pengantar Python Recursive Function

Meskipun rekursi tampaknya seperti prosedur yang rumit, itu tidak terlalu rumit. Dalam istilah awam, anggap Anda memiliki dua persegi panjang A dan B. Jika Anda menambahkannya bersama, mereka membentuk persegi panjang C. Ini sendiri merupakan prosedur rekursif. Kita telah menggunakan contoh yang lebih kecil dari persegi panjang untuk mendefinisikan dirinya sendiri, dan jika kita menulis fungsi Python, itu akan menjadi seperti berikut:

1	def rectangle(a,b):
2	return a+b
3

Karena fungsi rekursif memanggil dirinya sendiri, perlu ada aturan atau breakpoint di mana proses atau loop akan berakhir. Kondisi seperti ini dikenal sebagai base condition. Base condition base adalah persyaratan dalam setiap program rekursif, jika tidak prosedur akan menghasilkan loop tak terbatas.

Persyaratan kedua adalah kasus rekursif ketika fungsi memanggil dirinya sendiri.

Mari kita lihat sebuah contoh:

Dalam contoh ini, Anda akan menulis fungsi faktorial yang mengambil bilangan bulat (positif) sebagai input. Faktorial dari angka diperoleh dengan mengalikan angka dengan semua bilangan bulat positif di bawahnya. Misalnya, faktorial (3) = 3 x 2 x 1, faktorial (2) = 2 x 1, dan faktorial (0) = 1.

Hal pertama yang harus dilakukan adalah mendefinisikan base case kita, yang akan menjadi faktorial (0) = 1.

Seperti yang Anda lihat di atas, ada hubungan antara masing-masing skenario faktorial berturut-turut. Anda harus memperhatikan bahwa faktorial (4) = 4 x faktorial (3). Demikian pula, faktorial (5) = 5 x faktorial (4).

Bagian kedua akan menulis fungsi yang memanggil dirinya sendiri.

Sekarang setelah kita menyederhanakannya, fungsi yang dihasilkan adalah:

def factorial(n):
    if(n == 0):
    #Define our base case?
		return 1  
	else:
		return n*factorial(n-1) 
		
print(factorial(5))

#result 

# 120

Solusinya jika n == 0 adalah:

def factorial(n):
    if(n == 0):
      #Define our base case?
		return 1  
	else:
		return n*factorial(n-1) 
		
print(factorial(0))

#result 

# 0

Sekarang setelah Anda tahu cara menulis fungsi rekursif, mari kita lihat beberapa studi kasus yang akan memperkuat pemahaman Anda tentang rekursi.

Studi Kasus 1: Fibonacci

Dalam urutan Fibonacci, setiap angka adalah penjumlahan dari dua angka sebelumnya, seperti: 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5; 3 + 5 = 8. Urutan Fibonacci telah diterapkan di banyak area, dan yang paling umum adalah dalam memprediksi aksi harga di pasar saham oleh trader forex.

Urutan Fibonacci dimulai dengan 0 dan 1. Angka pertama dalam urutan Fibonacci adalah 0, angka kedua adalah 1, dan suku ketiga dalam urutan adalah 0 + 1 = 1. Yang keempat adalah 1 + 1 = 2 dan seterusnya .

Untuk mendapatkan fungsi rekursif, Anda harus memiliki dua kasus dasar, yaitu 0 dan 1. Anda kemudian dapat menerjemahkan pola penambahan ke dalam kotak yang lain.

Fungsi yang dihasilkan adalah:

def fibonacci(n):
    if(n == 1):
	  #define Base case 1 
		return 0+1 
	elif(n == 2):
	  #define Base case 1 
		return 1+2 
	else:
		return fibonacci(n) + fibonacci(n-1)
		
print(fibonacci(5))

#result

# 

Studi Kasus 2: Membalikkan String

Dalam contoh ini, Anda akan menulis fungsi yang mengambil string sebagai input dan kemudian mengembalikan kebalikan dari string.

Hal pertama yang harus dilakukan adalah mendefinisikan base case kita, yang akan memeriksa apakah string sama dengan 0 dan, jika demikian, akan mengembalikan string itu sendiri.

Langkah kedua adalah secara rekursif memanggil fungsi sebaliknya untuk memotong bagian dari string yang tidak termasuk karakter pertama dan kemudian menggabungkan karakter pertama ke ujung string yang diiris.

Fungsi yang dihasilkan adalah seperti yang ditunjukkan di bawah ini:

def reverse(a):
  
    if len(a) == 0:
        return a
    else:
        return reverse(a[1:]) + a[0]

print(reverse("Python is a very easy language to learn"))

# result

#nrael ot egaugnal ysae yrev a si nohtyP



Studi kasus 3: Jumlah Elemen

Dalam contoh ini, Anda akan menulis fungsi yang mengambil array sebagai input dan kemudian mengembalikan jumlah elemen dalam daftar.

Hal pertama yang harus dilakukan adalah mendefinisikan base case kita, yang akan memeriksa apakah ukuran daftar nol, dan mengembalikan 0 jika Benar.

Langkah kedua mengembalikan elemen dan panggilan ke fungsi sum () minus satu elemen dari daftar.

Solusinya adalah seperti yang ditunjukkan di bawah ini:

def sum_of_numbers(l):
   if len(l) == 1:
        return 0
   else:
        return l[0] + sum(l[1:])
        
a =[5,7,3,8,10]

print(sum(a))

# result
# 33

Solusi untuk daftar kosong seperti yang ditunjukkan di bawah ini:

def sum_of_numbers(l):
   if len(l) == 1:
        return 0
   else:
        return l[0] + sum(l[1:])
        

b =[]
 
print(sum(b))

# result

# 0

Kesimpulan

Tutorial ini telah mencakup apa yang diperlukan untuk menggunakan rekursi untuk memecahkan program-program kompleks dengan Python. Penting juga untuk dicatat bahwa rekursi memiliki keterbatasannya sendiri:

Rekursi membutuhkan banyak ruang stack, sehingga membuatnya agak lambat untuk mempertahankan program.
Fungsi rekursi membutuhkan lebih banyak ruang dan waktu untuk dieksekusi.

Ingat, jangan ragu untuk melihat apa yang kita miliki untuk dijual dan untuk belajar di Pasar Envato, dan silakan ajukan pertanyaan dan berikan umpan balik Anda yang berharga menggunakan umpan di bawah ini.