dotnet-musahibe-suallari-toplusu--rekursiyalar

.NET müsahibə sualları toplusu: Rekursiyalar

Alqoritmlər və Verilənlər strukturunu(Data Structures) öyrənən zaman qarşınıza çıxacaq konsepsiyalardan biri Rekursiyalardır. Musahibə suallarında isə sizə veriləcək alqoritmik tapşırıqların bir qismini rekursiyalar vasitəsilə rahatlıqla yerinə yetirə bilərsiniz.

               Bu məqaləmizdə rekursiyalar və onların bəzi alqoritmlərin həllində iştirakı, rekursiyaların müsbət və mənfi tərəfləri haqqında danışacağıq.

               İlk öncə onu deyim ki, rekursiyalar alqoritm deyil, onlar sadəcə alqoritminlərin həllində istifadə olunan konsepsiyadır. Rekursiyaların praktikada əhəmiyyəti , onların verilən tapşırığı alt tapşırıqlara parçalayaraq həll etmələrindən qaynaqlanır.

               Rekursiyalar yazdığımız metodun(funksiya) özü özünü təkrar çağırması prosesidir.

İlk baxışdan qəribə səslənsə də bir sıra alqoritmik məsələləri həll edən zaman, həmin məsələnin fərqli arqumentlə çağrılan eyni ardıcıllıqdan ibarət olduğunu görürük. Bu zaman rekursiyaları istifadə etmək tam yerinə düşər.

               Dediklərimizi aydınlıq gətirmək üçün ƏBOBun(Ən böyük ortaq bölən) tapılmasının Evklid alqoritmini rekursiya vasitəsilə həll edək . Deməli Evklid alqoritmində sadə formada deyilir ki, əgər iki ədədin ƏBOBunu tapmaq istəyiriksə sonda 0 alınana qədər böyük ədəddən kiçik ədədi çıxmaq lazımdır.

Misal : ƏBOB(18, 8)

18-8 = 10 // fərq çıxılandan böyükdür. Ona görə növbəti addımda 10-8 olacaq

10-8= 2 //fərq çıxılandan azdır. Ona görə növbəti addımda 8-2 olacaq

8-2 = 6

6-2 =4

4-2=2

2-2=0// sıfırın alınmasını təmin edən ədəd yəni 2 burada ƏBOBdur

Deməli ƏBOB(18, 8) = 2 olur.

 //Greatest Common Divisor without recursion
        static int GCD(int first, int second)
        {
            while(first!=0 && second!=0)
            {
                if (first > second)
                    first = first - second;
                else
                    second = second - first;
            }
            return Math.Max(first, second);
        }

Məsələnin həllinə diqqətlə baxsaq görərik ki, alqoritmin addımları təkrarlanır amma hər dəfəsində fərqli fərqli parametrlərlə.

Deməli əgər alqoritmdə təkrarlanan eyni addım olarsa və bu təkrarlanmalar bir birindən sadəcə argumentə görə fərqlənərsə ozaman Rekursiya istifadə etmək olar.

 //Greatest Common Divisor with Recursion
        static int GCDWithRecursion(int first, int second)
        {
            //base part
            if (first == 0)
                return second;


            //recursion part
            if (first > second)
                return GCDWithRecursion(second, first - second);
            else
                return GCDWithRecursion(second, second - first);
        }

Rekursiyalar 2 hissədən ibarət olur. Qəlib hissə(base part or base case) vasitəsilə hansı şərt daxilində rekursiyanın bitəcəyini göstəririk. Rekursiv hissədə isə(Recursion part or recursion case) öncəki şərt ödənilməzsə funksiyanın təkrar özünü çağırması tələb olunur.

Bu məqalədəki misallarda və ümumiyyətlə rekursiyalarda base case-i yazmaq mütləqdir. Əks halda rekursiya sonsuz dövrə girərək stackoverflow yaradır.

Müsahibədə alqoritmlərdən sizə veriləcək suallardan bir digərləri Faktorial və Fibanoççi ədədləri ilə bağlıdır. Bu iki məsələni də rekursiv yolla həll etmək olur.

İlk öncə faktorialın hesablanmasına baxaq. Faktorial, ədədin özündən əvvəlki ədədlərlə vurulması prosesidir. Misal: 1*2*3*4*5 = 120 . Deməli 5 ədədinin faktorialı 120-yə bərabərdir.

 Aşağıdakı iki nümunə for və while dövrləri ilə faktorialın yazılmasıdır.

	 static int FactorialWithWhile(int number)
        {
            int sum = 1;
            while(number!=1)
            {
                sum = sum *= number;
                number--;
            }
            return sum;
        }


        static int FactorialWithFor(int number)
        {
            int sum = 1;
            for(int i=1;i<=number;i++)
            {
                sum *= i;
            }
            return sum;
        }

İndi isə faktorialı rekursiya vasitəsilə həll edək.

	 static int FactorialRecursion(int number)
        {
            //base part
            if (number == 1)
                return number;


            else //recursion part
                return number * FactorialRecursion(number - 1);
        }

Yuxarıdakı misalı daha aydın izah edək. Rekursiv əməliyyat stek yaddaş sahəsi ilə işləyir. Beləki hər dəfə metod(funksiya) özü özünü çağıran zaman ona əlavə stek yaddaş sahəsi ayrılır və rekursiv proses base case-ə qədər stekdə funksiyaya yer ayırır.

Ən dibə (burada base case) çatdıqdan sonra funksiya geriyə, yuxarıya doğru aldığı nəticələri qaytarmağa başlayır . Bizim faktorial misalında funksiya number dəyişəninin 0 və 1 qiymətində geriyə 1 qaytarır. Funksiya dib hissədən yuxarıya doğru addımladıqca şəkildən göründüyü kimi 2,6 və 24 rəqəmlərini geri qaytarır. (1* 2 * 3 * 4) faktorial 5 olan zaman isə 5* 24 yəni 120 rəqəmini geri ala bilirik. Çunki number * factorial(number-1) yazmışıq. number = 5 olarsa, 5 * factorial(4)= 5 * 24 = 120 olacaq.


Digər bir misalımız Fibanoççi ədədləri ilə bağlıdır. Fibanoççi ədədləri 1 1 2 3 5 8 13 21... şəklində gedir. Hər bir ədəd özündən əvvəlki 2 ədədin cəminə bərabərdir.

Misal: Yuxarıda 5 ədədi özündən əvvəlki 2 və 3 ədədlərinin cəminə bərabərdir.


	 static int Fibanocci(int number)
        {
            int num1 = 0;
            int num2 = 1;
            int num3 = 0;
           
            int result = 0;
            for (int i = 1; i <= number; i++)
            {
                num3 = num2 + num1;
                num1 = num2;
                num2 = num3;
                result = num3;
            }
            return result;
        }

İndi isə rekursiya ilə fibanoççi ədədini tapaq.

	  static int FibanocciRec(int number)
        {
            //base part
            if (number <= 0) return 0;
            else if (number == 1) return 1;
            //recursion part
           else return FibanocciRec(number - 1) + FibanocciRec(number - 2);
        }

Bəs nəyə görə göstərdiyimiz nümunələri təkcə rekursiya ilə yazmadıq? Nümunələrdən aydın olduğu kimi bilməyinizi istəyirəm ki, rekursiya ilə yazacağınız istənilən bir alqoritmi iterativ yolla həll etmək olur!!

Madamki rekursiya olmadan da məsələni həll etmək olur, ozaman nə üçün rekursiya istifadə etməliyik? Bu sualı cavabında demək istəyirəm ki, rekursiyaların istifadəsinin həm mənfi həm də müsbət tərəfləri var.


 Gəlin rekursiyaların istifadəsinin müsbət tərflərinə baxaq:

1)Rekursiyalar kod təkrarının qabağını alır, bununla da yazdığımız addımı təkrar yazmaqdan bizi xilas edir

2)Rekursiyalar çox vaxt kodu daha oxunaqlı vəziyyətə salır


               Rekursiyaların istifadəsinin mənfi tərəfləri:

1)Yeni başlayanlar üçün kodun oxunmasını çətinləşdirir

2) Əlavə stek yaddaş sahəsi tələb edir və bəzi hallarda bəzi məsələlərin həlli üçün çox stek tələb olunduğuna görə, həmçinin base part(base case)=i düzgün göstərmədikdə stackoverflow exception yaradır.


Rekursiyaları nə zaman istifadə edək:

1)     Alqoritmlərdə Tree-lər, sorting və search alqoritmlərini daha asan yaza bilmək üçün

2)     Alqoritmlərdə parçala və hökm et(divide and conquer) prinsipi ilə rastlaşan zaman

3)     Hər zaman Tree və və Tree məntiqli alqoritm yerinə yetirən zaman

4)     Hər bir problemi alt problemə parçalayan zaman əgər həmin alt problem əsas problemin sadəə fərqli arqument qəbul edən variantı olaraq ortaya çıxarsa

Tural

Tural Süleymani

Süleymani Tural Microsoft-un MCSD statuslu mütəxəssisidir, 2008-ci ildən bu yana proqramlaşdırma üzrə tədris aparır

Müəllifin bu dildə ən son postları

Bu yazıları da bəyənə bilərsiniz