rust_algorithms/other/

recursion.rs

//! Rekursiya — funksiyaning o'zini o'zi chaqirishi.
//!
//! ## Har bir rekursiv funksiyada 2 qism bo'lishi shart
//!
//! 1. **Baza holati (base case)** — rekursiya to'xtaydigan joy. Bo'lmasa → stack overflow;
//! 2. **Rekursiv qadam** — masalani **kichikroq** ko'rinishga keltirish.
//!
//! ```text
//! faktorial(4)
//!  → 4 × faktorial(3)
//!        → 3 × faktorial(2)
//!              → 2 × faktorial(1)
//!                    → 1 × faktorial(0)
//!                          → 1          ← baza
//!  = 4 × 3 × 2 × 1 × 1 = 24
//! ```
//!
//! ## Rekursiya narxi
//!
//! Har bir chaqiruv **stack** da joy egallaydi. Rustda odatiy stack 8 MB —
//! taxminan bir necha yuz ming chaqiruvga yetadi. Chuqurlik katta bo'lsa,
//! iterativ variantga o'ting (Rust hozircha *tail call optimization* qilmaydi).

/// Faktorial: `n! = n × (n-1) × … × 1`, `0! = 1`.
///
/// Overflow bo'lsa `None`.
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::factorial;
///
/// assert_eq!(factorial(5), Some(120));
/// assert_eq!(factorial(0), Some(1));
/// assert_eq!(factorial(25), None);
/// ```
pub fn factorial(n: u32) -> Option<u64> {
    if n == 0 {
        return Some(1); // baza holati
    }
    factorial(n - 1)?.checked_mul(n as u64)
}

/// Sodda rekursiv Fibonachchi — **qanday qilmaslik** kerakligining namunasi.
///
/// Har bir chaqiruv ikkita yangi chaqiruv yaratadi → **O(2ⁿ)**.
/// `fib_naive(40)` bir necha soniya, `fib_naive(60)` esa bir necha yil ishlaydi.
///
/// Yechim: memoizatsiya ([`crate::dp::fib_memo`]) yoki iteratsiya
/// ([`crate::numbers::fibonacci`]).
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::fib_naive;
///
/// assert_eq!(fib_naive(10), 55);
/// // fib_naive(50) ni chaqirmang — juda uzoq davom etadi!
/// ```
pub fn fib_naive(n: u32) -> u64 {
    if n < 2 {
        return n as u64;
    }
    fib_naive(n - 1) + fib_naive(n - 2)
}

/// Hanoy minoralari: `n` ta diskni `from` ustunidan `to` ustuniga ko'chirish qadamlari.
///
/// **Qoidalar:** bir vaqtda bitta disk; katta disk kichigining ustiga qo'yilmaydi.
///
/// **Rekursiv g'oya (3 qadam):**
/// 1. Yuqoridagi `n-1` diskni yordamchi ustunga ko'chir;
/// 2. Eng katta diskni maqsad ustunga qo'y;
/// 3. `n-1` diskni yordamchidan maqsadga ko'chir.
///
/// - **Qadamlar soni:** `2ⁿ − 1` — bundan kamiga iloji yo'q (isbotlangan).
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::hanoi;
///
/// let qadamlar = hanoi(3, 'A', 'C', 'B');
/// assert_eq!(qadamlar.len(), 7); // 2³ − 1
/// assert_eq!(qadamlar[0], ('A', 'C'));
/// ```
pub fn hanoi(n: u32, from: char, to: char, aux: char) -> Vec<(char, char)> {
    let mut qadamlar = Vec::new();
    fn go(n: u32, from: char, to: char, aux: char, out: &mut Vec<(char, char)>) {
        if n == 0 {
            return;
        }
        go(n - 1, from, aux, to, out);
        out.push((from, to));
        go(n - 1, aux, to, from, out);
    }
    go(n, from, to, aux, &mut qadamlar);
    qadamlar
}

/// Satrni rekursiv teskari o'girish (o'quv maqsadida).
///
/// Amalda: `s.chars().rev().collect::<String>()`.
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::reverse_string;
///
/// assert_eq!(reverse_string("salom"), "molas");
/// assert_eq!(reverse_string(""), "");
/// ```
pub fn reverse_string(s: &str) -> String {
    let belgilar: Vec<char> = s.chars().collect();
    fn go(b: &[char]) -> String {
        match b.split_first() {
            None => String::new(),
            Some((birinchi, qolgan)) => format!("{}{}", go(qolgan), birinchi),
        }
    }
    go(&belgilar)
}

/// Ackermann funksiyasi — rekursiyaning "chegarasi".
///
/// Bu funksiya **primitiv rekursiv emas**: uni tsikllar bilan (oldindan ma'lum
/// takrorlanishlar soni bilan) yozib bo'lmaydi. Juda tez o'sadi:
/// `A(4, 2)` ≈ 2·10¹⁹⁷²⁸ — koinotdagi atomlardan ko'p raqamli son.
///
/// Shu sababli faqat kichik argumentlar bilan chaqiring (`m <= 3`).
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::ackermann;
///
/// assert_eq!(ackermann(1, 1), 3);
/// assert_eq!(ackermann(2, 3), 9);
/// assert_eq!(ackermann(3, 3), 61);
/// ```
pub fn ackermann(m: u64, n: u64) -> u64 {
    if m == 0 {
        n + 1
    } else if n == 0 {
        ackermann(m - 1, 1)
    } else {
        ackermann(m - 1, ackermann(m, n - 1))
    }
}

/// Ikkilik qidiruvning rekursiv ko'rinishi (`start..end` oralig'ida).
///
/// "Bo'l va hukmronlik qil" ning eng sodda namunasi.
///
/// # Misol
/// ```
/// use rust_algorithms::other::recursion::binary_search_rec;
///
/// let v = [1, 3, 5, 7, 9];
/// assert_eq!(binary_search_rec(&v, 7), Some(3));
/// assert_eq!(binary_search_rec(&v, 4), None);
/// ```
pub fn binary_search_rec(list: &[i64], target: i64) -> Option<usize> {
    fn go(list: &[i64], target: i64, lo: usize, hi: usize) -> Option<usize> {
        if lo >= hi {
            return None; // baza: oraliq bo'sh
        }
        let mid = lo + (hi - lo) / 2;
        match list[mid].cmp(&target) {
            std::cmp::Ordering::Equal => Some(mid),
            std::cmp::Ordering::Less => go(list, target, mid + 1, hi),
            std::cmp::Ordering::Greater => go(list, target, lo, mid),
        }
    }
    go(list, target, 0, list.len())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn faktorial() {
        assert_eq!(factorial(1), Some(1));
        assert_eq!(factorial(10), Some(3_628_800));
        assert_eq!(factorial(20), Some(2_432_902_008_176_640_000));
        assert_eq!(factorial(21), None);
    }

    #[test]
    fn fib_naive_kichik_qiymatlarda() {
        let kutilgan = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34];
        for (n, &k) in kutilgan.iter().enumerate() {
            assert_eq!(fib_naive(n as u32), k);
        }
    }

    #[test]
    fn hanoy_qadamlari_qoidaga_mos() {
        for n in 1..=8u32 {
            let qadamlar = hanoi(n, 'A', 'C', 'B');
            assert_eq!(qadamlar.len(), (1 << n) - 1);

            // Simulyatsiya: qoidalar buzilmasligini tekshiramiz
            let mut ustunlar = std::collections::HashMap::from([
                ('A', (1..=n).rev().collect::<Vec<u32>>()), // pastda katta
                ('B', Vec::new()),
                ('C', Vec::new()),
            ]);
            for (from, to) in qadamlar {
                let disk = ustunlar.get_mut(&from).unwrap().pop().expect("bo'sh ustun");
                let maqsad = ustunlar.get_mut(&to).unwrap();
                if let Some(&ust) = maqsad.last() {
                    assert!(disk < ust, "katta disk kichigining ustiga qo'yildi");
                }
                maqsad.push(disk);
            }
            assert_eq!(ustunlar[&'C'].len(), n as usize);
        }
    }

    #[test]
    fn satrni_teskari() {
        assert_eq!(reverse_string("abc"), "cba");
        assert_eq!(reverse_string("a"), "a");
        assert_eq!(reverse_string("o'zbek"), "kebz'o");
    }

    #[test]
    fn ackermann_kichik_qiymatlar() {
        assert_eq!(ackermann(0, 0), 1);
        assert_eq!(ackermann(1, 0), 2);
        assert_eq!(ackermann(2, 2), 7);
        assert_eq!(ackermann(3, 2), 29);
    }

    #[test]
    fn rekursiv_binary_search() {
        let v: Vec<i64> = (0..100).map(|x| x * 2).collect();
        for (i, &x) in v.iter().enumerate() {
            assert_eq!(binary_search_rec(&v, x), Some(i));
        }
        assert_eq!(binary_search_rec(&v, 1), None);
        assert_eq!(binary_search_rec(&[], 1), None);
    }
}