Rekursiya anlayışı

1.1 Rekursiyanın tərifi və əsas konseptləri.

Rekursiya — bu, nəyinsə özünü təkrarən yerinə yetirməsi deməkdir. Təsəvvür et ki, səndə bir təlimat var və bu təlimatın bir hissəsi o təlimata əməl etməyi deyir. Bu elə bil sən özünə əmri təkrarlamağı əmr edirsən.

Real həyatdan nümunələr:

Bir-birinə qarşı duran güzgülər:

Təsəvvür et ki, sən iki güzgü arasında dayanmısan. Öz əksini görürsən, və əksində də öz əksini görürsən, və bu belə davam edir. Bu, güzgünün digər güzgünün əksini göstərdiyindən rekursiyaya bir nümunədir.

Matryoşkalar:

Matryoşka — içində başqa bir matryoşka olan kukladır, o birisin içində başqa biri və s. Ən kiçik kuklayadək gedəndə artıq açmağa heç nə qalmır. Bu o deməkdir ki, rekursiyada bazis vəziyyəti — dayanma anı olur.

Pizza bölmək:

Təsəvvür elə ki, sən pizza iki yerə bölürsən. Sonra bir parçanı götürüb yenidən iki yerə bölürsən, və beləcə davam edirsən, ta ki parça elə kiçik olur ki, bölmək olmaz. Bölmək prosesi rekursivdir, amma parçanı daha bölə bilmədiyin an — bazis vəziyyətidir.

Vacibdir! Rekursiya – bu sonsuz əmrlərin təkrarı deyil, əksinə, mürəkkəb tapşırığın hissələrə bölünməsi və bu tapşırığın hissələrini həll etmə üsulunun bütöv tapşırığın həllinə bənzəməsidir.

Bu necə işləyir?

Rekursiyanı başa düşmək üçün iki əsas anlayışı bilmək vacibdir:

• Bazis vəziyyəti: bu, rekursiyanın sona çatdığı şərtdir. Məsələn, matryoşka nümunəsində bazis vəziyyəti odur ki, ən kiçik matryoşkanı açırsan və içərisində heç nə yoxdur.
• Rekursiv vəziyyət: bu, məsələnin kiçik hissələrlə təkrarlanmasıdır. Pizza nümunəsində sən bir parçanı bölürsən, sonra onun yarısını bölürsən və belə davam edir.

Niyə bu faydalıdır?

Rekursiya mürəkkəb məsələləri daha sadə hissələrə ayıraraq həll etməyə kömək edir. Bütün bir tapşırığı eyni anda həll etmək əvəzinə, onu hissə-hissə edirsən.

Həyatdan digər nümunələr:

Nağıl içində nağıl:

Təsəvvür elə ki, nağılın qəhrəmanı başqa bir nağıl danışır, və həmin nağılın qəhrəmanı daha bir nağıl danışır. Nağıllardan biri bitəndə sən əvvəlki nağıla qayıdırsan. Bazis vəziyyət — son nağıl bitəndə olur.

Rekursiv şəkil:

Böyük bir üçbucaq çəkirsən, sonra bu üçbucağın hər bir küncündə kiçik bir üçbucaq çəkirsən və bu şəkildə davam edirsən, ta ki üçbucaqlar çox kiçik olur və artıq çəkilməz. Bazis vəziyyət — üçbucaq o qədər kiçik olur ki, çəkilə bilmir.

1.2 Əsas hal: tərif və nümunələr.

Əsas hal — bu, rekursiv çağırışları dayandıran və funksiyanın konkret bir dəyəri qaytarmasına imkan verən şərtdir. Adətən, bu, məsələnin ən sadə və aydın həllidir, yəni problem artıq rekursiya tələb etmir.

Əsas hal nümunələri:

Ədədin faktorialı:

n ədədinin faktorialı belə göstərilir: F(n) == 1*2*3*…*n. Həmçinin aydındır ki, F(n) == n* F(n-1).

Əsas hal: ədədin faktorialı 0 və ya 1 bərabərdir 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Əsas hal
    else:
        return n * factorial(n - 1)
        

Fibonacci ədədləri:

Fibonacci ədədləri – bu bir sıra: 1, 1, 2, 3, 5, 8, 13, … Hər növbəti ədəd iki əvvəlki ədədin cəminə bərabərdir. Yəni, F(n) == F(n-1) + F(n-2)

Əsas hal: Fibonacci ədədlərindən ilk ikisi 1-ə bərabərdir, bu səbəbdən «sıfırıncı» Fibonacci ədədi 0-a bərabərdir. Və ya F(0) = 0 və F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Əsas hal
    elif n == 1:
        return 1  # Əsas hal
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Rekursiv hal: tərif və nümunələr

Rekursiv hal — bu, funksiyanın bir hissəsidir ki, məsələni özünün yenidən çağırılması ilə həll edir və yeni parametrlərlə həllin baza halına yaxınlaşmasını təmin edir. Hər rekursiv çağırış məsələni azaldır və ya dəyişdirir ki, nəticədə baza halına çatır.

Rekursiv hal nümunələri:

Ədədin faktorialı:

Rekursiv hal: n ədədinin faktorialı n vurulsun n-1 ədədinin faktorialına bərabərdir.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Baza hal
    else:
        return n * factorial(n - 1)  # Rekursiv hal
        

Fibonacci ədədləri:

Rekursiv hal: F(n), F(n-1) və F(n-2)-nin cəminə bərabərdir.

def fibonacci(n):
    if n == 0:
        return 0  # Baza hal
    elif n == 1:
        return 1  # Baza hal
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Rekursiv hal
        

1.4 Rekursiv alqoritmlərin nümunələri

1. İkili ağacın keçilməsi:

"in-order" ardıcıllıqla keçmə nümunəsi.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# İstifadə nümunəsi:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Siyahıda maksimum elementi tapmaq:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Əsas hal
    else:
        max_of_rest = find_max(lst[1:])  # Rekursiv hal
        return max(lst[0], max_of_rest)
        
# İstifadə nümunəsi:
print(find_max([1, 5, 3, 9, 2]))  # Çıxış: 9
        
        

3. Rekursiv ikili axtarış:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Əsas hal: element tapılmadı
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Əsas hal: element tapıldı
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Rekursiv hal
    else:
        return binary_search(arr, target, left, mid - 1)  # Rekursiv hal 
# İstifadə nümunəsi:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Çıxış: 4