Rekursi Python

Dalam tutorial ini, Anda akan belajar membuat fungsi rekursif (fungsi yang memanggil dirinya sendiri).

Apa itu rekursi?

Rekursi adalah proses mendefinisikan sesuatu dalam dirinya sendiri.

Contoh dunia fisik adalah menempatkan dua cermin paralel yang saling berhadapan. Objek apa pun di antaranya akan dipantulkan secara rekursif.

Fungsi Rekursif Python

Dalam Python, kita tahu bahwa suatu fungsi dapat memanggil fungsi lain. Bahkan dimungkinkan bagi fungsi untuk memanggil dirinya sendiri. Jenis konstruksi ini disebut sebagai fungsi rekursif.

Gambar berikut menunjukkan cara kerja fungsi rekursif yang disebut recurse .

Berikut adalah contoh fungsi rekursif untuk mencari faktorial suatu bilangan bulat.

Faktorial suatu bilangan adalah hasil kali semua bilangan bulat dari 1 sampai dengan bilangan tersebut. Misalnya, faktorial dari 6 (dilambangkan dengan 6!) adalah 1*2*3*4*5*6 =720 .

Contoh fungsi rekursif

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

Keluaran

The factorial of 3 is 6

Pada contoh di atas, factorial() adalah fungsi rekursif saat memanggil dirinya sendiri.

Ketika kita memanggil fungsi ini dengan bilangan bulat positif, ia akan memanggil dirinya sendiri secara rekursif dengan mengurangi angkanya.

Setiap fungsi mengalikan angka dengan faktorial angka di bawahnya sampai sama dengan satu. Panggilan rekursif ini dapat dijelaskan dalam langkah-langkah berikut.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Mari kita lihat gambar yang menunjukkan proses langkah demi langkah dari apa yang terjadi:

Rekursi kami berakhir ketika jumlahnya berkurang menjadi 1. Ini disebut kondisi dasar.

Setiap fungsi rekursif harus memiliki kondisi dasar yang menghentikan rekursi atau fungsi tersebut memanggil dirinya sendiri secara tak terbatas.

Interpreter Python membatasi kedalaman rekursi untuk membantu menghindari rekursi tak terbatas, yang mengakibatkan stack overflow.

Secara default, kedalaman rekursi maksimum adalah 1000 . Jika melewati batas, hasilnya RecursionError . Mari kita lihat salah satu syaratnya.

def recursor():
    recursor()
recursor()

Keluaran

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Keuntungan Rekursi

Fungsi rekursif membuat kode terlihat bersih dan elegan.
Tugas yang kompleks dapat dipecah menjadi sub-masalah yang lebih sederhana menggunakan rekursi.
Pembuatan urutan lebih mudah dengan rekursi daripada menggunakan beberapa iterasi bersarang.

Kekurangan Rekursi

Terkadang logika di balik rekursi sulit untuk diikuti.
Panggilan rekursif mahal (tidak efisien) karena menghabiskan banyak memori dan waktu.
Fungsi rekursif sulit untuk di-debug.

Argumen Fungsi Python Fungsi Python Anonim/Lambda

Python