7-bo'lim: Rekursiya¶

_{↑ Mundarijaga qaytish}

🧠 Rekursiyada xotira odatda chaqiruv steki (call stack) chuqurligiga teng. Juda chuqur rekursiya stack overflow beradi — Pythonda standart limit ~1000.

92. Yig'indi 1..n (rekursiv)¶

⏱ O(n) · 💾 O(n) — stek chuqurligi.

JS

const sumTo = n => n === 0 ? 0 : n + sumTo(n - 1);

PHP

function sumTo($n) {
    return $n === 0 ? 0 : $n + sumTo($n - 1);
}

Python

def sum_to(n):
    return 0 if n == 0 else n + sum_to(n - 1)

93. Massiv yig'indisi (rekursiv)¶

⏱ O(n) · 💾 O(n) Eslatma: indeks orqali — slicing (arr[1:]) ishlatilsa har chaqiruvda O(n) nusxa olinib, jami O(n²) bo'lardi.

JS

const sumArr = (arr, i = 0) => i === arr.length ? 0 : arr[i] + sumArr(arr, i + 1);

PHP

function sumArr($arr, $i = 0) {
    return $i === count($arr) ? 0 : $arr[$i] + sumArr($arr, $i + 1);
}

Python

def sum_arr(arr, i=0):
    return 0 if i == len(arr) else arr[i] + sum_arr(arr, i + 1)

94. Daraja (rekursiv power) base^exp¶

⏱ O(e) · 💾 O(e) Eslatma: tez darajalash (b^(e/2) ni kvadratga ko'tarish) bilan O(log e) ga tushadi.

JS

const power = (b, e) => e === 0 ? 1 : b * power(b, e - 1);

PHP

function power($b, $e) {
    return $e === 0 ? 1 : $b * power($b, $e - 1);
}

Python

def power(b, e):
    return 1 if e == 0 else b * power(b, e - 1)

95. Fibonachchi (rekursiv, n-element)¶

⏱ O(2ⁿ) · 💾 O(n) Eslatma: sodda rekursiya eksponensial — bitta qiymat qayta-qayta hisoblanadi. Memoizatsiya (DP) bilan O(n) bo'ladi (14-bo'lim).

JS

const fib = n => n < 2 ? n : fib(n - 1) + fib(n - 2);

PHP

function fib($n) {
    return $n < 2 ? $n : fib($n - 1) + fib($n - 2);
}

Python

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Quyidagi chaqiruv daraxti nega sodda rekursiya eksponensial ekanini ko'rsatadi — bir xil qiymatlar (masalan fib(3), fib(2)) qayta-qayta hisoblanadi:

fib(5) rekursiya chaqiruv daraxti va takroriy hisoblar

96. Satrni teskari (rekursiv)¶

⏱ O(n) · 💾 O(n)

JS

const reverse = s => s === "" ? "" : reverse(s.slice(1)) + s[0];

PHP

function reverse($s) {
    return $s === "" ? "" : reverse(substr($s, 1)) . $s[0];
}

Python

def reverse(s):
    return "" if s == "" else reverse(s[1:]) + s[0]

97. Raqamlar yig'indisi (rekursiv)¶

⏱ O(d) · 💾 O(d) — d: raqamlar soni.

JS

const digitSum = n => n === 0 ? 0 : n % 10 + digitSum(Math.floor(n / 10));

PHP

function digitSum($n) {
    return $n === 0 ? 0 : $n % 10 + digitSum(intdiv($n, 10));
}

Python

def digit_sum(n):
    return 0 if n == 0 else n % 10 + digit_sum(n // 10)

98. Palindrom (rekursiv tekshirish)¶

⏱ O(n) · 💾 O(n)

JS

const isPalindrome = s =>
  s.length <= 1 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1));

PHP

function isPalindrome($s) {
    if (strlen($s) <= 1) return true;
    return $s[0] === $s[strlen($s) - 1] && isPalindrome(substr($s, 1, -1));
}

Python

def is_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

99. Massivda chiziqli qidiruv (rekursiv)¶

⏱ O(n) · 💾 O(n) — topilsa indeks, aks holda −1.

JS

const search = (arr, x, i = 0) =>
  i === arr.length ? -1 : arr[i] === x ? i : search(arr, x, i + 1);

PHP

function search($arr, $x, $i = 0) {
    if ($i === count($arr)) return -1;
    return $arr[$i] === $x ? $i : search($arr, $x, $i + 1);
}

Python

def search(arr, x, i=0):
    if i == len(arr):
        return -1
    return i if arr[i] == x else search(arr, x, i + 1)

100. Massivdagi eng katta (rekursiv)¶

⏱ O(n) · 💾 O(n)

JS

const maxOf = (arr, i = 0) =>
  i === arr.length - 1 ? arr[i] : Math.max(arr[i], maxOf(arr, i + 1));

PHP

function maxOf($arr, $i = 0) {
    if ($i === count($arr) - 1) return $arr[$i];
    return max($arr[$i], maxOf($arr, $i + 1));
}

Python

def max_of(arr, i=0):
    if i == len(arr) - 1:
        return arr[i]
    return max(arr[i], max_of(arr, i + 1))

101. Hanoy minorasi (Tower of Hanoi)¶

⏱ O(2ⁿ) · 💾 O(n) — harakatlar ketma-ketligini qaytaradi.

JS

const hanoi = (n, from = "A", to = "C", via = "B", moves = []) => {
  if (n === 0) return moves;
  hanoi(n - 1, from, via, to, moves);
  moves.push(`${from} -> ${to}`);
  hanoi(n - 1, via, to, from, moves);
  return moves;
};

PHP

function hanoi($n, $from = "A", $to = "C", $via = "B", &$moves = []) {
    if ($n === 0) return $moves;
    hanoi($n - 1, $from, $via, $to, $moves);
    $moves[] = "$from -> $to";
    hanoi($n - 1, $via, $to, $from, $moves);
    return $moves;
}

Python

def hanoi(n, frm="A", to="C", via="B", moves=None):
    if moves is None:
        moves = []
    if n == 0:
        return moves
    hanoi(n - 1, frm, via, to, moves)
    moves.append(f"{frm} -> {to}")
    hanoi(n - 1, via, to, frm, moves)
    return moves

102. Barcha permutatsiyalar (permutations)¶

⏱ O(n · n!) · 💾 O(n · n!) Eslatma: amaliyotda Pythonda itertools.permutations ishlatiladi.

JS

const permutations = arr => {
  if (arr.length <= 1) return [arr];
  return arr.flatMap((x, i) =>
    permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(p => [x, ...p]));
};

PHP

function permutations($arr) {
    if (count($arr) <= 1) return [$arr];
    $result = [];
    foreach ($arr as $i => $x) {
        $rest = array_merge(array_slice($arr, 0, $i), array_slice($arr, $i + 1));
        foreach (permutations($rest) as $p) {
            array_unshift($p, $x);
            $result[] = $p;
        }
    }
    return $result;
}

Python

def permutations(arr):
    if len(arr) <= 1:
        return [arr]
    result = []
    for i, x in enumerate(arr):
        for p in permutations(arr[:i] + arr[i + 1:]):
            result.append([x] + p)
    return result

103. Quvvat to'plami (power set — barcha kichik to'plamlar)¶

⏱ O(2ⁿ) · 💾 O(2ⁿ)

JS

const powerSet = arr => {
  if (arr.length === 0) return [[]];
  const rest = powerSet(arr.slice(1));
  return [...rest, ...rest.map(s => [arr[0], ...s])];
};

PHP

function powerSet($arr) {
    if (count($arr) === 0) return [[]];
    $first = $arr[0];
    $rest = powerSet(array_slice($arr, 1));
    $withFirst = array_map(fn($s) => array_merge([$first], $s), $rest);
    return array_merge($rest, $withFirst);
}

Python

def power_set(arr):
    if not arr:
        return [[]]
    rest = power_set(arr[1:])
    return rest + [[arr[0]] + s for s in rest]

104. O'nlikni ikkilikka (rekursiv)¶

⏱ O(log n) · 💾 O(log n)

JS

const toBinary = n => n < 2 ? String(n) : toBinary(Math.floor(n / 2)) + (n % 2);

PHP

function toBinary($n) {
    return $n < 2 ? (string) $n : toBinary(intdiv($n, 2)) . ($n % 2);
}

Python

def to_binary(n):
    return str(n) if n < 2 else to_binary(n // 2) + str(n % 2)