Recursion

Dasturlashda o'z-o'zini chaqiruvchi funksiya rekursiv funksiya deb ataladi va bu uslub rekursiya (recursion) deyiladi.

Oddiy ko'rinishda rekursiv funksiya quyidagicha bo'ladi:

func recurse() {
    // kodlar
    recurse() // o'zini o'zi qayta chaqirish
}

1. Cheksiz rekursiya xavfi

Agar rekursiv funksiya to'xtash shartisiz chaqirilsa, u cheksiz davom etadi va dastur xotirasini to'ldirib yuboradi:

package main

import "fmt"

func countDown(number int) {
    fmt.Println(number)
    // To'xtash shartisiz rekursiv chaqiruv
    countDown(number - 1)
}

func main() {
    countDown(3)
}

Ushbu kod cheksiz ravishda manfiy sonlarni chop etishda davom etadi: 3, 2, 1, 0, -1, -2...

2. To'xtash sharti (Stopping Condition) bilan rekursiya

Cheksiz rekursiyaning oldini olish uchun har doim if...else orqali to'xtash sharti (baza sharti) qo'yiladi:

package main

import "fmt"

func countDown(number int) {
    if number > 0 {
        fmt.Println(number)
        // Rekursiv chaqiruv
        countDown(number - 1)
    } else {
        // Rekursiya to'xtaydi
        fmt.Println("Vaqt tugadi!")
    }
}

func main() {
    countDown(3)
}

Natija:

3
2
1
Vaqt tugadi!

Qanday ishlaydi:

1. countDown(3): 3 > 0 rost, 3 chop etiladi va countDown(2) chaqiriladi.
2. countDown(2): 2 > 0 rost, 2 chop etiladi va countDown(1) chaqiriladi.
3. countDown(1): 1 > 0 rost, 1 chop etiladi va countDown(0) chaqiriladi.
4. countDown(0): 0 > 0 yolg'on, else bloki ishlab "Vaqt tugadi!" yozuvi chiqadi va rekursiya yakunlanadi.

3. Misol: 1 dan N gacha sonlar yig'indisini hisoblash

package main

import "fmt"

func sum(number int) int {
    // Rekursiyani to'xtatish sharti
    if number == 0 {
        return 0
    } else {
        return number + sum(number-1)
    }
}

func main() {
    var num = 50
    result := sum(num)

    fmt.Println("Yig'indi:", result)
}

Natija:

Yig'indi: 1275

Tushuntirish:

• Birinchi chaqiruvda: 50 + sum(49)
• Ikkinchi chaqiruvda: 50 + 49 + sum(48)
• Oxirida number == 0 bo'lganda return 0 bajariladi va umumiy yig'indi 1275 hisoblanadi.

4. Misol: Sonning faktorialini topish

Sonning faktoriali n! = n × (n-1) × ... × 1 bo'lib, 0! = 1 ga teng.

package main

import "fmt"

func factorial(num int) int {
    // To'xtash sharti: 0 ning faktoriali 1 ga teng
    if num == 0 {
        return 1
    } else {
        // Rekursiv ko'paytirish
        return num * factorial(num-1)
    }
}

func main() {
    number := 3
    result := factorial(number)

    fmt.Printf("%d ning faktoriali: %d\n", number, result)
}

Natija:

3 ning faktoriali: 6

Bu yerda hisoblash quyidagicha kechadi: 3 * factorial(2) → 3 * 2 * factorial(1) → 3 * 2 * 1 * 1 = 6