Rekursiya və İterasiya

Proqramlaşdırmanın əsaslarını öyrənməyə başlayanda, adətən, ilk yazdığımız proqram "Hello, world!" sətirini çap edir. Sonra dəyişənlər, operatorlar, funksiyalarla tanış oluruq. Və adətən, bir başlanğıcçı ilk tanış olduğu operatorlar şərt operatoru və dövr operatorudur. Dərhal, bəzi sadə funksiya yazmaq istəyi yaranır: bir ədədin faktorialı, qüvvətə yüksəltmək, və ya binomial əmsalın hesablanması. Çox hallarda, bir başlanğıc proqramçı funksiyaların iterativ versiyasını həyata keçirir. Lakin, az adam bilir ki, hər hansı iterativ funksiya həmçinin rekursiv olaraq da həyata keçirilə bilər.

Rekursiya - proqramın (və ya funksiyanın) özünü birbaşa və ya digər proqramlar (funksiyalar) vasitəsilə çağırması ilə məlumatların emal təşkilatının bir üsuludur.

Bir funksiya rekursiv adlanır əgər, onun emalı zamanı, birbaşa və ya dolayısıyla, digər funksiyaların çağırışları zəncirinə vasitəsilə yenidən çağırılır.

Iterasiya - bəzi əməliyyatların təkrarlanaraq icra edildiyi, lakin rekursiv proqramların (funksiyaların) çağırışlarına səbəb olmayan məlumatların emal təşkilatının bir üsuludur.

Teorem. Hər hansı bir alqoritm rekursiv formada həyata keçirilə bilərsə, iterativ formada da yenidən yazıla bilər və əksinə.

Aşağıda, dövr operatorlarından və rekursiv yanaşmadan istifadə edərək həyata keçirilmiş bir sıra elementar funksiyaları nəzərdən keçirəcəyik. Hər hansı bir proqramlaşdırma dilində rekursiv funksiyaları yazmadan əvvəl, adətən, funksiyaların hesablanma metodunu müəyyən edən bir rekursiya əlaqəsi yazmaq lazımdır. Rekursiya əlaqəsi ən azı iki şərt ehtiva etməlidir:

I) rekursiyanın davam etdirilməsi şərti (rekursiya addımı);

II) rekursiyanın bitməsi şərti.

Rekursiya, funksiyanın özünə çağırışı ilə həyata keçiriləcək. Bu halda, rekursiyanın davam etdirilməsi şərti funksiyanın bədənində ilk növbədə yoxlanılmalıdır. Əgər bu doğrudursa, onda funksiyadan çıxırıq. Əks halda, rekursiv addım edirik.

Funksiyaların iterativ versiyası for dövr operatorundan istifadə edilərək həyata keçiriləcək.

1. Bir ədədin faktorialı. Mənfi olmayan tam ədəd $n$-in faktorialı 1-dən $n$-ə qədər bütün təbii ədədlərin hasilidir və $n$! ilə işarə olunur. Əgər $f(n)=n$!, onda aşağıdakı rekursiya əlaqəsi tutulur:

Birinci tənlik rekursiyanın addımını – $f(n)$-in $f(n-1)$ vasitəsilə hesablanma metodunu təsvir edir. İkinci tənlik funksiyanın hesablanmasının nə zaman dayandırılacağını göstərir. Əgər müəyyən edilməsə, onda funksiya sonsuz işləyəcək.

Məsələn, $f(3)$ dəyəri aşağıdakı kimi hesablanıla bilər:

$f(3)=3\cdot f(2)=3\cdot 2\cdot f(1)=3\cdot 2\cdot 1\cdot f(0)=3\cdot 2\cdot 1\cdot 1=6$

Aydındır ki, $f(n)$-i hesablamaq üçün $n$ rekursiv çağırış etmək lazımdır.

Dövri həyata keçirilmənin ideyası bir ədədin faktorialını dövr operatorundan istifadə edərək birbaşa hesablamaqdır:

$f(n)=1\cdot 2\cdot 3\cdot \dots \cdot n$

2. Bir ədədin qüvvəti xətti zamanda. Bir ədədin qüvvətini $f(a,n)=a^n$ xətti (O($n$)) zaman qiymətləndirməsi ilə hesablamaq aşağıdakı rekursiya əlaqəsi ilə müəyyən edilə bilər:

İterativ versiyada, kifayətdir ki, $a\cdot a\cdot \dots \cdot a$ ($n$ ədəd $a$ amili) hasilini hesablayaq.

3. Bir ədədin qüvvəti loqarifmik zamanda. Bir ədədin qüvvətini $f(a,n)=a^n$ zaman qiymətləndirməsi O(log${}_{2}n$) olaraq müəyyən edilir:

Məsələn, onuncu qüvvətə yüksəltmək belə həyata keçirilə bilər:

Kvadrata yüksəltmək bir çarpmanı təmsil etdiyi üçün, $a^{10}$-u hesablamaq üçün 4 çarpma kifayətdir.

4. Bir ədədin rəqəmlərinin cəmi. Təbii ədəd $n$-in rəqəmlərinin cəmi $f(n)$ funksiyası ilə aşağıdakı kimi tapıla bilər:

Rekursiyanın davam etdirilməsi şərti: bir ədədin rəqəmlərinin cəmi o ədədin son rəqəmi ilə son rəqəmi olmayan ədədin (ədəd 10-a bölünmüşdür) rəqəmlərinin cəminə bərabərdir.

Rekursiyanın bitməsi şərti: Əgər ədəd 0-dırsa, onda onun rəqəmlərinin cəmi 0-dır.

Məsələn, 234 ədədinin rəqəmlərinin cəmi aşağıdakı kimi hesablanacaq:

$f(234)=4+f(23)=4+3+f(2)=4+3+2+f(0)=4+3+2+0=9$

5. Birliklərin sayı. Ədədin ikilik təmsilindəki birliklərin sayı $f(n)$ funksiyası ilə aşağıdakı kimi hesablanıla bilər (& - bitvi 'VƏ' əməliyyatı):

Əməliyyat n = n & (n – 1) nəticəsində ədədin ikilik təmsilindəki son birlik məhv edilir:

$n=a_1{a}_2\dots a_{k-1}{a}_{k}10\dots 0$

$n–1=a_1{a}_2\dots a_{k-1}{a}_{k}01\dots 1$

n & (n – 1) = a_1a_2…a_{k-1} 000…0

Funksiyanın $f$ rekursiv çağırışı ədədin ikilik təmsilindəki birliklərin sayı qədər ediləcək.

6. Binomial əmsal. Binomial əmsalın dəyəri

aşağıdakı rekursiya əlaqəsi ilə müəyyən edilir:

int c(int k, int n){ if (n == k) return 1; if (k == 0) return 1; return c(k - 1, n - 1) + c(k, n - 1);}

Nəzərə alaraq ki,

binomial əmsalın dəyəri dövr vasitəsilə hesablana bilər. Bu halda, bütün bölünmə əməliyyatları tam olacaq. Əgər $k>n–k$, onda hesablama zamanı Məhdudiyyət Zamanını keçməmək üçün

münasibətindən istifadə edin.

int Cnk(int k, int n){ long long res = 1; if (k > n - k) k = n - k; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; return (int)res;}

7. Rekursiv funksiya. Verilmiş təbii $n$ üçün $f(n)$ funksiyasının dəyərini aşağıdakı rekursiya əlaqələri ilə hesablayaq:

$f(2\cdot n)=f(n),$

$f(2\cdot n+1)=f(n)+f(n+1),$

$f(0)=0,f(1)=1$

Funksiyanın $f(n)$ birbaşa həyata keçirilməsi belədir:

int f(int n){ if (n <= 1) return n; if (n % 2) return f(n / 2) + f(n / 2 + 1); return f(n / 2);}

Bu həyata keçirilmədə, $f$ funksiyasının bəzi dəyərləri bir neçə dəfə hesablanıla bilər. $f$-in dəyərlərini hesablamaq üçün başqa bir yanaşmanı nəzərdən keçirək. Funksiyanı

$g(n,i,j)=i\cdot f(n)+j\cdot f(n+1),$

üçün aşağıdakı bərabərliklər tutulur:

$g(2\cdot n,i,j)=g(n,i+j,j),$

$g(2\cdot n+1,i,j)=g(n,i,i+j),$

$g(0,i,j)=i\cdot f(0)+j\cdot f(1)=j$

Verilən əlaqələrdən istifadə edərək, $f(n)=g(n,1,0)$ dəyəri zaman qiymətləndirməsi O(log $n$) ilə hesablana bilər.

int g(int n, int i, int j){ if (!n) return j; if (n % 2) return g(n / 2, i, i + j); return g(n / 2, i + j, j);}

int f(int n){ return g(n, 1, 0);}

8. Ackermann funksiyası. Ackermann funksiyası A($m$, $n$) aşağıdakı kimi rekursiv olaraq müəyyən edilir:

A(0, $n$) = $n$ + 1,

A($m$, 0) = A($m$ – 1, 1),

A($m$, $n$) = A($m$ – 1, A($m$, $n$ – 1))

Ackermann funksiyasının rekursiv həyata keçirilməsi belədir:

int a(int m, int n){ if (!m) return n + 1; if (!n) return a(m - 1, 1); return a(m - 1, a(m, n - 1));}

Kiçik $m$ dəyərləri üçün, Ackermann funksiyası açıq şəkildə ifadə edilə bilər:

A(0, $n$) = $n$ + 1

A(1, $n$) = 2 + ($n$ + 3) – 3 = $n$ + 2

A(2, $n$) = 2 · ($n$ + 3) – 3 = 2 · $n$ + 3

A(3, $n$) = 2${}^{n+3}$ – 3

9. Kəşfiyyat üçün seçim [ACM, 1999]. Sıraya düzülmüş $n$ əsgərdən bir neçəsini kəşfiyyata seçmək lazımdır. Bunun üçün aşağıdakı əməliyyat icra edilir: əgər sırada 3-dən çox əsgər varsa, onda cüt mövqelərdə dayanan bütün əsgərlər çıxarılır, və ya tək mövqelərdə dayanan bütün əsgərlər çıxarılır. Bu prosedur sırada 3 və ya daha az əsgər qalana qədər təkrarlanır. Onlar kəşfiyyata göndərilirlər. Bu cür kəşfiyyat qruplarının yaradılma yollarının sayını hesablayın.

Giriş. Sırada dayanan əsgərlərin sayı $n$ (0 < $n$ ≤ 10${}^7$).

Çıxış. Əsgərlərin yuxarıda göstərilən şəkildə kəşfiyyata seçilmə yollarının sayı.

Həll. $f(n)$ ilə sırada dayanan $n$ adamdan kəşfiyyat qruplarının yaradılma yollarının sayını işarə edək. Yalnız üç kəşfiyyatçıdan maraqlandığımız üçün, $f(1)=0$, $f(2)=0$, $f(3)=1$. Yəni, üç adamdan yalnız bir qrup yaradıla bilər, bir və ya iki adamdan heç biri.

Əgər $n$ cütdürsə, onda problemə görə sırada dayanan əsgərləri çıxardıqdan sonra, ya cüt mövqelərdə dayanan $n$ / 2 əsgər, ya da tək mövqelərdə dayanan $n$ / 2 əsgər qalacaq. Beləliklə, cüt $n$ üçün $f(n)=2\cdot f(n/2)$.

Əgər $n$ təkdirsə, onda çıxarmaqdan sonra, ya cüt mövqelərdə dayanan $n$ / 2 əsgər, ya da tək mövqelərdə dayanan $n$ / 2 + 1 əsgər qalacaq. Tək $n$ üçün cəmi yolların sayı bərabərdir

$f(n)=f(n/2)+f(n/2+1).$

Beləliklə, $f(n)$-in dəyərini hesablamaq üçün əldə edilmiş rekursiya formulunu:

$f(n)=2\cdot f(n/2)$, əgər $n$ cütdürsə

$f(n)=f(n/2)+f(n/2+1)$, əgər $n$ təkdirsə

$f(1)=0,f(2)=0,f(3)=1$

$f$ funksiyasının həyata keçirilməsi belədir:

int f(int n){ if (n <= 2) return 0; if (n == 3) return 1; if (n % 2) return f(n / 2) + f(n / 2 + 1); return 2 * f(n / 2);}

MƏNBƏLƏR

1. "Alqoritmlər: Dizayn və Analiz", Cormen T., Leiserson C., Rivest R., Stein C., – Moskva, Sankt-Peterburq, Kiyev, 2005 – 1292 s.

2. "Proqramlaşdırmanın Praktikası və Teorisi", Kitab2. "Proqramlaşdırmanın Praktikası və Teorisi", Cild 2. Vinokurov N.A., Vorozhtsov A.V., - Moskva: Fizmatkniga, 2008 - 288 s.