Rekursiv funktsiyalar

Rekursiv funktsiyalar

Rekursiv funktsiyalar-bu o'zlarini chaqiradigan funktsiyalar. Bunday funktsiyalar ko'pincha turli xil ko'rinishlarni chetlab o'tish uchun ishlatiladi. Masalan, agar biz papkada ma'lum bir faylni topishimiz kerak bo'lsa, unda avval ushbu papkadagi barcha fayllarni ko'rib chiqamiz, so'ngra uning barcha pastki qismlarini ko'rib chiqamiz

Masalan, faktorial hisoblashni rekursiv funktsiya sifatida aniqlaymiz:

Faktorial funktsiyasida, agar n raqami 1 dan katta bo'lsa, u holda bu raqam n-1 raqami parametr sifatida uzatiladigan bir xil funktsiyaning natijasiga ko'paytiriladi. Ya'ni, rekursiv tushish sodir bo'ladi. Va hokazo, parametr qiymati 1 ga teng bo'lmagan nuqtaga yetguncha. Bunday holda, funktsiya 1 ni qaytaradi.

Rekursiv funktsiya return operatoridan foydalanadigan va ushbu funktsiyaning qolgan qo'ng'iroqlarining bajarilishi yaqinlashadigan ba'zi bir asosiy variantga ega bo'lishi kerak. Faktorial holatida asosiy variant n \ u003d 1 bo'lgan vaziyat bilan ifodalanadi. Bunday holda, return 1; ko'rsatmasi ishlaydi.
Masalan, factorial(5) ni chaqirganda quyidagi qo'ng'iroqlar zanjiri olinadi:

5 * factorial(4)

5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Rekursiv funksiyaning yana bir keng tarqalgan indikativ misoli Fibbonachchi raqamlarini hisoblaydigan funksiyadir. Fibonachchi raqamlari ketma-ketligining n-chi a'zosi quyidagi formula bilan aniqlanadi: f(n)=f(n-1) + f(n-2) bunda f(0)=0 va f(1)=1. Demak F(0)=0 va f(1)=1 qiymatlari shu bilan berilgan funktsiya uchun asosiy variantlarni aniqlaydi:

Dasturning natijasi-fibbonachchi ketma-ketligidan konsolga 10 ta raqamni chiqarish:

Yuqoridagi misollarda funktsiya to'g'ridan-to'g'ri o'zini chaqirdi. Ammo funktsiyani rekursiv chaqirish ham bilvosita bo'lishi mumkin. Masalan, fun1 () funktsiyasi boshqa fun2 () funktsiyasini chaqiradi, bu esa o'z navbatida fun1 () ni keltirib chiqaradi. Bunday holda fun1() va fun2() funktsiyalari o'zaro rekursiv funktsiyalar deb ham ataladi.

Shuni ta'kidlash kerakki, ko'pincha rekursiv funktsiyalar tsikl shaklida ifodalanishi mumkin. Masalan, faktorial hisoblash uchun rekursiya o'rniga biz sikldan foydalanamiz:

Va ko'pincha tsiklik dizaynlar reksursiyadan ko'ra samaraliroqdir. Misol uchun, agar funktsiya o'zini minglab marta chaqirsa, har bir qo'ng'iroq uchun argument qiymatlari va qaytish manzili nusxalarini saqlash uchun katta hajmdagi Stack xotirasi kerak bo'ladi, bu esa dastur uchun ajratilgan Stack xotirasini tezda tugatishiga olib kelishi mumkin, chunki Stack xotirasi odatda sobit va cheklangan. bu dasturning ishdan chiqishiga olib kelishi mumkin. Shuning uchun, bunday hollarda, odatda, tsikl kabi muqobil yondashuvlardan foydalanish yaxshiroqdir. Biroq, qo'shimcha xarajatlarga qaramay, rekursiyadan foydalanish ko'pincha dastur yozishni ancha osonlashtirishi mumkin.