Rekursiv alqoritmlər

2.1 Fayl ağacını gəzmə

Gəlin fayl ağacını gəzmək üçün rekursiv bir alqoritmi nəzərdən keçirək. Alqoritm kataloqu və bütün alt kataloqları gəzəcək, bütün faylların və qovluqların siyahısını çıxaracaq.

import os

def list_files_recursive(directory, indent=0):
    # Cari kataloqda olan bütün fayl və qovluqların siyahısını alırıq
    items = os.listdir(directory)
                
    for item in items:
        # Fayl və ya qovluq üçün tam yolu yaradırıq
        path = os.path.join(directory, item)
                    
        # Strukturun görünüşünü yaxşılaşdırmaq üçün məsafə ilə çap edirik
        print(' ' * indent + item)
                    
        # Əgər bu bir qovluqdursa, onun tərkibini rekursiv olaraq gəzirik
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# İstifadə nümunəsi
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Bu necə işləyir?

1. Funksiya list_files_recursive(directory, indent=0):
   • directory — məzmununu göstərmək istədiyimiz cari kataloq.
   • indent — faylların və qovluqların yuvalanmasını göstərmək üçün cari məsafə səviyyəsi.
2. Cari kataloqdakı bütün faylların və qovluqların siyahısını alırıq os.listdir(directory) istifadə edərək.
3. Siyahıdakı hər bir elementi iterasiya edirik items.
4. Element üçün tam yol yaradırıq os.path.join(directory, item) istifadə edərək.
5. Elementin adını məsafə ilə çap edirik ki, bu məsafə yuvalanma səviyyəsinə görə 4 boşluq artır.
6. Elementin qovluq olub olmadığını yoxlayırıq os.path.isdir(path) istifadə edərək. Əgər bəli, rekursiv olaraq list_files_recursive(path, indent + 4) çağırırıq ki, onun tərkibini gəzək.

Çıxış nümunəsi:

Tutaq ki, bizdə aşağıdakı kataloq strukturu var:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

list_files_recursive(root_directory) funksiyasını icra edərkən biz aşağıdakı çıxışı alacağıq:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

Bu alqoritm kataloq ağacını rekursiv olaraq gəzib çıxarır və bütün faylları və qovluqları onların yuvalanma səviyyəsinə uyğun olaraq göstərir.

2.2 Hanoi Qüllələri

“Hanoi Qüllələri” məsələsi

Hanoi qüllələri — bu, bir stajdan digərinə diskləri köməkçi stajdan istifadə edərək hərəkət etdirmək üzərində qurulmuş klassik rekursiv tapşırıqdır.

Qaydalar:

1. Yalnız bir diski bir dəfə hərəkət etdirmək olar.
2. Disk boş bir stajın üzərinə və ya daha böyük ölçüdə bir diskin üzərinə yerləşdirilə bilər.
3. Bütün disklər bir stajdan digərinə köməkçi stajdan istifadə edərək hərəkət etdirilməlidir.

Bu məsələnin həlli üçün rekursiv bir alqoritm:

Hanoi qüllələri alqoritmi məsələləri aşağıdakı kimi həll edir:

1. n - 1 diski ilkin stajdan köməkçi staja, hədəf stajını istifadə edərək hərəkət etdirin.
2. Qalan diski ilkin stajdan hədəf staja hərəkət etdirin.
3. n - 1 diski köməkçi stajdan hədəf staja, ilkin stajını istifadə edərək hərəkət etdirin.

Python-da nümunə

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Disk 1-i {source}-dən {target}-ə hərəkət etdirin")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Disk {n}-i {source}-dən {target}-ə hərəkət etdirin")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# İstifadə nümunəsi:
n = 3  # Disklərin sayı
hanoi_tower(n, 'A', 'C', 'B')
        

Bu necə işləyir?

Baz vəziyyət:

Yalnız bir disk varsa (n == 1), onu ilkin stajdan hədəf staja sadəcə hərəkət etdirmək olar.

if n == 1:
    print(f"Disk 1-i {source}-dən {target}-ə hərəkət etdirin")
    return

Rekursiv vəziyyət:

Addım 1. n-1 diski ilkin stajdan köməkçi stajına, hədəf stajını istifadə edərək hərəkət etdirmək.

hanoi_tower(n - 1, source, auxiliary, target)

Addım 2. Disk n-i ilkin stajdan hədəf staja hərəkət etdirmək.

print(f"Disk {n}-i {source}-dən {target}-ə hərəkət etdirin")

Addım 3. n - 1 diski köməkçi stajdan hədəf staja, ilkin stajını istifadə edərək hərəkət etdirmək.

hanoi_tower(n - 1, auxiliary, target, source)

Nümunə çıxışı:

Üç disk üçün (n = 3) A, B və C stajlarında, proqram aşağıdakı çıxışı verəcək:

Disk 1-i A-dan C-yə hərəkət etdirin
Disk 2-ni A-dan B-yə hərəkət etdirin
Disk 1-i C-dən B-yə hərəkət etdirin
Disk 3-ü A-dan C-yə hərəkət etdirin
Disk 1-i B-dən A-ya hərəkət etdirin
Disk 2-ni B-dən C-yə hərəkət etdirin
Disk 1-i A-dan C-yə hərəkət etdirin

2.3 Koç Qartopu

Rekursiyadan istifadə edərək qartopu çəkmək maraqlı bir tapşırıqdır, bu tez-tez fraqmentləri öyrənmək üçün istifadə edilir. Qartopu çəkməyin sadə yollarından biri də fraqmental bir əyri olan Koç əyrisindən istifadə etməkdir.

Koç Qartopunu çəkmək üçün alqoritm

Koç əyrisi belə qurulur:

• Bir düz xəttdən başlayırıq.
• Hər bir seqmenti üç hissəyə bölür və mərkəzi hissəni kiçik bir əyri ilə əvəz edirik, bu "bucağa" bənzəyir.
• Bu prosesi hər seqment üçün rekursiv olaraq təkrar edirik.

Addım-addım təlimat

• Başlanğıc: Başlanğıc seqmenti çəkin.
• Bölünmə: Hər seqmenti üç hissəyə bölün.
• Mərkəzi hissəni əvəz edin: Mərkəzi hissədə 60 dərəcə bir bucaq əmələ gətirən iki xətdən ibarət "bucaq" çəkin.
• Prosesin təkrarlanması: Bu prosesi hər bir seqment üçün davam etdirin.

Turtle kitabxanasından istifadə edərək Python nümunəsi

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Ekranın konfiqurasiyası
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Turtle-ın konfiqurasiyası
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Qartopu çəkirik
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Çəkilişi tamamlayırıq
turtle.done()
            

Bu necə işləyir?

1. draw_koch_curve(t, length, depth) funksiyası:

• t: çəkən turtle-dır.
• length: seqmentin uzunluğudur.
• depth: detaldan asılı olan rekursiyanın dərinliyidir.

2. Əsas hal:

Əgər depth 0-a bərabərdirsə, turtle düz seqment çəkir.

if depth == 0:
    t.forward(length)
        

3. Rekursiv hal:

Seqmenti üç hissəyə ayırırıq və hər hissəyə draw_koch_curve funksiyasını rekursiv olaraq tətbiq edirik, döngələr əlavə edirik.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. draw_snowflake(t, length, depth) funksiyası:

Üç Koç əyrisini bir qar topusunda birləşdirir.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

Kodu necə işə salmaq olar?

• Turtle kitabxanasının quraşdırıldığından əmin olun (pip install PythonTurtle).
• Kodu .py faylına köçürüb yapışdırın və işə salın. Ekranda qar topusunun çəkilişini görəcəksiniz.

Bu alqoritm rekursiyanın və həndəsi quruluşların sadə prinsiplərindən istifadə edərək qar topusunun fraqmental strukturunu vizuallaşdırmağa imkan verir.