Swiftda Rekursiya

Biror funksiyaning o'zi-o'zini chaqirishi rekursiv funksiya deyiladi. Bu texnika esa rekursiya deb ataladi.

Real hayotdagi misol: ikkita parallel ko'zguni bir-biriga qarama-qarshi qo'ying. Ularning orasiga biror buyum qo'yilsa, u cheksiz qayta aks etadi — bu rekursiyaga o'xshaydi.

Rekursiyaning ishlash tizimi

func recurse() {
  // ...  
  recurse()
  // ...     
}

recurse()

Bu yerda recurse() funksiyasi o'zi-o'zini qayta-qayta chaqirmoqda. Quyidagi rasm rekursiya qanday ishlashini ko'rsatadi:

Rekursiyani to'xtatish sharti

Agar rekursiyani to'xtatish uchun biror shart berilmasa, funksiya cheksiz o'zini chaqiraveradi.

Rekursiyani to'xtatish uchun odatda if...else ishlatiladi.

Har doim rekursiv funksiyada ikki bo'lak bo'ladi:

Rekursiv chaqiruv bo'lagi
Rekursiyani to'xtatadigan bo'lak

Misol:

Quyidagi dastur sonni 0 gacha kamaytirib boradi:

Swift•

Sonni 0 gacha sanab tushish

func countDown(number: Int) {
// sonni ekranga chiqarish
print(number)

// rekursiyani to'xtatish sharti
if number == 0 {
  print("Sanash to'xtadi")
}
// rekursiya sharti
else {
  // sonni kamaytirish
  countDown(number: number - 1)
}
}

print("Sanash:")
countDown(number: 3)

Bu misolda countDown() funksiyasi o'zi-o'zini chaqiraveradi, toki son 0 bo'lmaguncha.

number == 0 bo'lganda rekursiya to'xtaydi.

Dastur ishlash jarayoni:

Iteration	Function call	Print	number == 0 ?
1	countDown(3)	3	false
2	countDown(2)	2	false
3	countDown(1)	1	false
4	countDown(0)	0	true (rekursiya to'xtaydi)

Misol:

Swift•

Faktorial hisoblash

func factorial(num: Int) -> Int {
// rekursiyani to'xtatish sharti
if num == 0 {
  return 1
} 
// rekursiv chaqiruv
else {
  return num * factorial(num: num - 1)
}
}

let number = 3
let result = factorial(num: number)
print("3 ning faktoriali:", result)

Bu yerda rekursiv funksiya factorial() chaqiruv davomida num ni har safar 1 taga kamaytiradi.

Ishlash jarayoni:

num = 3 → chaqiradi factorial(2)
num = 2 → chaqiradi factorial(1)
num = 1 → chaqiradi factorial(0)
num = 0 → 1 qaytaradi va rekursiya orqaga yechila boshlaydi.

Rekursiya orqali faktorial hisoblash

Rekursiyaning afzalliklari va kamchiliklari

1. Afzalliklar

Kodimiz qisqa va toza ko'rinadi.
Ma'lum data structure va murakkab algoritmlarda (Graf va Tree traversal) rekursiya zarur.

2. Kamchiliklar

Iterativ dasturlarga qaraganda ko'proq stack xotira ishlatadi.
Ko'proq process vaqtini oladi.
Iterativ dasturlarga qaraganda debug qilish qiyinroq.

Birinchi masalaning yechimi

Keling, birinchi masala "Faktorial (rekursiv)" ni birga yechib ko'ramiz:

1-qadam: Masalani tushunish

n = 5 → 5! = 5 × 4 × 3 × 2 × 1 = 120
n = 0 → 0! = 1 (matematik qoida)

2-qadam: Yechim algoritmi

Base case: n == 0 bo'lsa 1 qaytaramiz
Rekursiv case: n * factorial(n - 1)

3-qadam: Kodni yozamiz

Swift•

Faktorial (rekursiv) yechimi

func factorial(n: Int) -> Int {
  // Base case
  if n == 0 {
      return 1
  }
  
  // Rekursiv case
  return n * factorial(n: n - 1)
}

// Test
print(factorial(n: 5))  // 120
print(factorial(n: 0))  // 1
print(factorial(n: 6))  // 720

Ishlash jarayoni (n = 5):

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1 * factorial(0)
             = 5 * 4 * 3 * 2 * 1 * 1
             = 120