Python Recursion

Rekursiya — biror narsani o'zi orqali ifodalash jarayoni.

Jismoniy dunyodagi misol sifatida ikkita parallel oynani bir-biriga qarshi qo'yishni olish mumkin. Ular orasidagi istalgan narsa rekursiv tarzda aks etadi.

Python rekursiv funksiyasi

Pythonda funksiya boshqa funksiyalarni chaqira olishini bilamiz. Hatto funksiyaning o'zini o'zi chaqirishi ham mumkin. Bunday konstruksiyalar rekursiv funksiyalar deb ataladi.

Quyidagi rasmda recurse nomli rekursiv funksiyaning ishlashi ko'rsatilgan.

Quyida integerning faktorialini topuvchi rekursiv funksiyaga misol keltirilgan.

Sonning faktoriali — 1 dan o'sha songacha bo'lgan barcha integerlarning ko'paytmasi. Masalan, 6ning faktoriali (6! deb belgilanadi) 1*2*3*4*5*6 = 720.

Rekursiv funksiyaga misol

def factorial(x):
    """Bu integerning faktorialini
    topuvchi rekursiv funksiya"""

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

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

Natija

The factorial of 3 is 6

Yuqoridagi misolda, factorial() — rekursiv funksiya, chunki u o'zini o'zi chaqiradi.

Bu funksiyani musbat integer bilan chaqirsak, u sonni kamaytirib borib, o'zini rekursiv ravishda chaqiraveradi.

Har bir funksiya sonni undan pastdagi sonning faktoriali bilan songa teng bo'lguncha ko'paytiradi. Bu rekursiv chaqiruvni quyidagi qadamlar orqali tushuntirish mumkin.

factorial(3)          # 3 bilan 1-chaqiruv
3 * factorial(2)      # 2 bilan 2-chaqiruv
3 * 2 * factorial(1)  # 1 bilan 3-chaqiruv
3 * 2 * 1             # number=1 bo'lgani uchun 3-chaqiruvdan qaytish
3 * 2                 # 2-chaqiruvdan qaytish
6                     # 1-chaqiruvdan qaytish

Keling, nima sodir bo'layotganining qadam-baqadam jarayonini ko'rsatuvchi rasmga qaraymiz:

Bizning rekursiyamiz son 1gacha kamayganda tugaydi. Bu bazaviy shart (base condition) deb ataladi.

Har bir rekursiv funksiya rekursiyani to'xtatuvchi bazaviy shartga ega bo'lishi shart, aks holda funksiya o'zini o'zi cheksiz chaqiraveradi.

Python interpretatori cheksiz rekursiyalarning oldini olish uchun rekursiya chuqurligini cheklaydi, bu esa stek to'lib ketishi (stack overflow)ga olib kelishi mumkin.

Standart holatda, rekursiyaning maksimal chuqurligi 1000. Agar bu chegara oshib ketsa, RecursionError yuz beradi. Keling, bunday holatga misolni ko'ramiz.

def recursor():
    recursor()
recursor()

Natija

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

Rekursiyaning afzalliklari

• Rekursiv funksiyalar kodni toza va nafis ko'rinishga keltiradi.
• Murakkab vazifani rekursiya yordamida soddaroq kichik muammolarga bo'lish mumkin.
• Ketma-ketlik generatsiya qilish rekursiya bilan ba'zi ichma-ich iteratsiyalarni ishlatishga qaraganda osonroq.

Rekursiyaning kamchiliklari

• Ba'zida rekursiya ortidagi mantiqni kuzatish qiyin.
• Rekursiv chaqiruvlar qimmatga tushadi (samarasiz), chunki ular ko'p xotira va vaqtni egallaydi.
• Rekursiv funksiyalarni sozlash (debug qilish) qiyin.

Ko'proq o'qing: Python Program to Find Sum of Natural Numbers Using Recursion, Python Program to Display Fibonacci Sequence Using Recursion, Python if...else Statement