Rekursiya

Rekursiya nima?

Rekursiya — bu funksiya muammoning kichikroq ko‘rinishini hal qilish uchun o‘zini o‘zi chaqirishi.

Bu muammo bevosita hal qilinadigan darajada kichik bo‘lguncha davom etadi. Ana shu eng kichik holat bazaviy holat (base case) deb ataladi.

Rekursiya misoli

Ikki sonni qo‘shish oson, lekin butun bir sonlar oralig‘ini qo‘shish murakkab bo‘lishi mumkin.

Rekursiya buni soddalashtiradi: vazifani har safar bitta sonni qo‘shishdan iborat qismlarga ajratamiz.

def sum_range(k):
  if k > 0:   # base case
    return k + sum_range(k - 1)
  else:
    return 0

result = sum_range(10)
print(result)   # 55

function sumRange(k) {
  if (k > 0) { // base case
    return k + sumRange(k - 1);
  } else {
    return 0;
  }
}

const result = sumRange(10);
console.log(result); // 55

public class Main {
  public static int sum(int k) {
    if (k > 0) { // base case
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }

  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);  // 55
  }
}

#include <iostream>
using namespace std;

int sum(int k) {
  if (k > 0) { // base case
    return k + sum(k - 1);
  } else {
    return 0;
  }
}

int main() {
  int result = sum(10);
  cout << result;  // 55
  return 0;
}

Misolni ishga tushirish »

Misol tushuntirilishi

sum(10) chaqirilganda, u 10 ni barcha kichikroq sonlar yig‘indisiga qo‘shadi, masalan:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + ... + 1 + sum(0)
10 + 9 + 8 + 7 + ... + 1 + 0

sum(0) shunchaki 0 qaytargani uchun rekursiya to‘xtaydi va natija hisoblanadi.

Teskari sanash misoli

Bu misol rekursiya yordamida 5 dan 1 gacha sonlarni kamayish tartibida chiqaradi:

def countdown(n):
  if n == 0:   # base case
    print("Done!")
  else:
    print(n)
    countdown(n - 1)   # recursive call

countdown(5)

function countdown(n) {
  if (n === 0) { // base case
    console.log("Done!");
  } else {
    console.log(n);
    countdown(n - 1); // recursive call
  }
}

countdown(5);

public class Main {
  static void countdown(int n) {
    if (n == 0) { // base case
      System.out.println("Done!");
    } else {
      System.out.println(n);
      countdown(n - 1); // recursive call
    }
  }
  public static void main(String[] args) {
    countdown(5);
  }
}

#include <iostream>
using namespace std;

void countdown(int n) {
  if (n == 0) { // base case
    cout << "Done!";
  } else {
    cout << n << endl;
    countdown(n - 1); // recursive call
  }
}

int main() {
  countdown(5);
  return 0;
}

Misolni ishga tushirish »

Faktorial misoli

Sonning faktoriali (n!) — bu 1 dan n gacha bo‘lgan barcha sonlarning ko‘paytmasi.

Misol: 5! = 5 * 4 * 3 * 2 * 1 = 120

Buni rekursiya yordamida tabiiy ravishda hal qilish mumkin:

def factorial(n):
  if n == 1:   # base case
    return 1
  else:
    return n * factorial(n - 1)

print(factorial(5))

function factorial(n) {
  if (n === 1) { // base case
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5));

public class Main {
  static int factorial(int n) {
    if (n == 1) { // base case
      return 1;
    } else {
      return n * factorial(n - 1);
    }
  }
  public static void main(String[] args) {
    System.out.println(factorial(5));
  }
}

#include <iostream>
using namespace std;

int factorial(int n) {
  if (n == 1) { // base case
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

int main() {
  cout << factorial(5);
  return 0;
}

Misolni ishga tushirish »

Xulosa

Rekursiya — bu funksiya o‘zini o‘zi chaqirishi.
Rekursiyani to‘xtatish uchun bazaviy holat kerak.
Rekursiya kichikroq, o‘xshash muammolarga bo‘linadigan masalalar (masalan, faktorial, papkalarni aylanib chiqish, daraxt/graf algoritmlari) uchun foydali.

Eslatma: Rekursiya kuchli vosita, lekin ehtiyotkorlik bilan yozilmasa, ko‘p xotira sarflashi mumkin. Har doim bazaviy holat mavjudligiga ishonch hosil qiling, aks holda rekursiya cheksiz davom etishi mumkin!

W3Schools Pathfinder

Yutuqlaringizni kuzating – bu bepul!

Ro'yxatdan o'tish Kirish