17. Recur — rekursiya

Barcha masalalar faqat rekursiv funksiya yordamida (sikl operatorlarisiz) yechilishi kerak.

Klassik rekursiya

1. Musbat butun son n berilgan. n! (faktorial) ni rekursiya bilan hisoblang.
Misol: n = 5 → 120

2. Ikki butun son a (a > 0) va n (n ≥ 0) berilgan. aⁿ ni rekursiya bilan hisoblang.
Misol: a = 2, n = 10 → 1024

3. n berilgan (n > 1). n-Fibonachchi sonini rekursiya bilan hisoblang.
Misol: n = 10 → 55

4. Ikki musbat butun son a, b berilgan. Ularning EKUBini Evklid algoritmi bo'yicha rekursiv funksiya bilan toping.
Misol: a = 48, b = 18 → 6

5. Musbat butun son n berilgan. 1 dan n gacha bo'lgan sonlar yig'indisini rekursiya bilan toping.
Misol: n = 100 → 5050

6. Musbat butun son n berilgan. Uning raqamlar sonini rekursiya bilan aniqlang.
Misol: n = 12345 → 5

7. Musbat butun son n berilgan. Uning raqamlari yig'indisini rekursiya bilan toping.
Misol: n = 12345 → 15

8. Musbat butun son n berilgan. Uni teskari tartibda (raqamlarini teskari o'qib) rekursiya bilan chiqaring.
Misol: n = 1234 → 4321

9. n berilgan. n-Lukas sonini rekursiya bilan hisoblang.
Misol: n = 5 → 11 (2 1 3 4 7 11)

10. n va k (0 ≤ k ≤ n) berilgan. Binomial koeffitsient C(n,k) ni rekursiya bilan (Paskal uchburchagi formulasi orqali) hisoblang.
Misol: n = 5, k = 2 → 10

Massiv va satr bilan rekursiya

11. Ro'yxat berilgan. Elementlar yig'indisini rekursiya bilan toping.
Misol: [1 2 3 4] → 10

12. Ro'yxat berilgan. Eng katta elementni rekursiya bilan toping.
Misol: [3 9 2 7] → 9

13. Satr berilgan. Uning palindrom ekanligini rekursiya bilan tekshiring.
Misol: level → True; salom → False

14. Satr berilgan. Uni rekursiya bilan teskari tartibda chiqaring.
Misol: salom → molas

15. Slice va X soni berilgan. X ro'yxatda bor-yo'qligini rekursiv qidiruv bilan aniqlang.
Misol: [4 8 15 16], X = 15 → True; X = 5 → False

16. Saralangan ro'yxat va X soni berilgan. X ni ikkilik qidiruv (binary search) rekursiv variant bilan toping.
Misol: [1 3 5 7 9 11], X = 7 → indeks 3

17. Ro'yxat berilgan. Uni rekursiya bilan (quick sort yoki merge sort) saralang.
Misol: [5 2 9 1] → [1 2 5 9]

18. Satr va C belgisi berilgan. C belgisi satrda necha marta uchrashini rekursiya bilan sanang.
Misol: banana, a → 3

Matematik rekursiya

19. m va n berilgan (kichik qiymatlar). Akkerman funksiyasi A(m, n) ni rekursiya bilan hisoblang.
\(\displaystyle A(m, n) = \begin{cases} n + 1, & m = 0,\\ A(m - 1,\, 1), & m > 0,\ n = 0,\\ A(m - 1,\, A(m,\, n - 1)), & m > 0,\ n > 0. \end{cases}\)
Misol: A(2, 3) → 9

20. n berilgan. Tarkibida ketma-ket ikkita 1 bo'lmagan, n uzunlikdagi ikkilik satrlar (0 va 1 lardan iborat) sonini rekursiya bilan toping.
Misol: n = 3 → 5 (000 001 010 100 101)

21. n berilgan. n-Katalan sonini rekursiv formula bilan hisoblang.
Misol: n = 5 → 42

22. m, n berilgan. Ikki sonning EKUKini rekursiya bilan (EKUB orqali) hisoblang.
Misol: 12, 18 → 36

23. n berilgan (n > 0). Garmonik yig'indi H(n) = 1 + 1/2 + … + 1/n ni rekursiya bilan hisoblang.
Misol: n = 4 → 2.0833

24. x va n berilgan. Teylor qatori bo'yicha sin(x) ni n ta had bilan rekursiv funksiya orqali hisoblang.
Misol: x = 1, n = 4 → 0.8415

25. n berilgan. 1 dan n gacha bo'lgan sonlarning barcha o'rin almashtirishlarini (perestanovkalarini) rekursiya bilan chiqaring.
Misol: n = 3 → 123 132 213 231 312 321

Amaliy va o'yin masalalari

26. N diskli "Hanoy minorasi" masalasini rekursiya bilan yeching va harakatlar sonini chiqaring.
Misol: N = 3 → 7

27. N ta pog'onali zinapoyaga chiqishda har safar 1 yoki 2 pog'ona bosib chiqish mumkin. Nechta xil usul borligini rekursiya bilan toping.
Misol: N = 5 → 8

28. To'g'ri to'rtburchak N×M katakli maydonda, faqat o'ngga yoki pastga yurib, chap yuqori burchakdan o'ng past burchakgacha nechta yo'l borligini rekursiya bilan toping.
Misol: N = 3, M = 3 → 6

29. n berilgan. n ni natural sonlar yig'indisi ko'rinishida yozish usullari sonini rekursiya bilan toping (qo'shiluvchilar tartibi ahamiyatsiz; masalan n = 4 uchun 5 ta usul).
Misol: n = 4 → 5; n = 5 → 7

30. Labirint (N×M matritsa, 0 — yo'l, 1 — devor) berilgan. Boshlang'ich nuqtadan chiqish nuqtasigacha yo'l borligini rekursiya (backtracking) bilan aniqlang.
Misol: 0 0 1 / 1 0 1 / 1 0 0, boshlang'ich (0, 0), chiqish (2, 2) → yo'l bor; 0 1 0 / 1 1 0 / 0 0 0 → yo'l yo'q