İterativ və rekursiv

İterativ və rekursiv:
Dinamik proqramlaşdırma həllinin qurulması üçün iki üsul var. Onlar aşağıdakılardır:
• İterativ (dövrlərdən istifadə etməklə)
• Rekursiv (rekursiyadan istifadə etməklə).
Rekursiya, proqramın birbaşa özünü çağırdığı və ya digər proqramların köməyi ilə məlumatların işlənməsini təşkil etmək üsuludur.
İterasiya məlumatların işlənməsinin təşkili üsuludur, burada müəyyən hərəkətlər rekursiv proqram çağırışlarına səbəb olmadan dəfələrlə təkrarlanır.
Funksional alqoritmik dillər rekursiyanı təşviq etməyə meyllidir. İterasiya ümumiyyətlə daha sürətli olur, bəzi proqram tərtibçiləri əslində müəyyən rekursiya kodunu iterasiyaya çevirirlər. Rekursiya çox vaxt iterasiyadan daha zərifdir.
Rekursiv proqramlaşdırma proqramçıya kodu elə təşkil etmək üçün daha yaxşı imkan verir ki, o, hesablamaların nəticələri yadda saxlanıla bilsin və məntiqi olaraq ardıcıl olsun.
Rekursiya yaddaş baxımından daha baha başa gəlir, çünki hər bir rekursiv çağırış adətən yaddaş ünvanının stekə (yığına) əlavə edilməsini tələb edir ki, proqram daha sonra həmin nöqtəyə qayıda bilsin.
Əsas fərq: Proqramlaşdırmada rekursiya rekursiv funksiya ilə izah edilə bilər. Rekursiv funksiya kodu təkrarlamaq üçün özünü yenidən çağıran funksiyadır. Digər tərəfdən, iterasiya kodun bəzi bölmələrində dövrə vuran iterasiya funksiyası ilə əldə edilir.
Proqramlaşdırmada təkrara nail olmaq üçün rekursiya və iterasiyadan istifadə olunur. Onlar dəfələrlə təkrarlanan bir prosesə istinad edirlər. Rekursiya, şərt yerinə yetirilənə qədər bir şeyin özünə istinad etdiyi yanaşmaya əsaslanır. Metod özünü birbaşa və ya dolayı yolla çağıra bildiyi halda rekursiv adlanır.
Sadə dillə desək, rekursiya bir dövrəyə nail olmaq üçün funksiyanı dəfələrlə çağırır. İterasiya, dövrəni həyata keçirən funksiyada xüsusi kod parçasıdır və iterasiya ilə normal dövrə arasındakı fərq ondan ibarətdir ki, dövrə kodunda əməliyyatda iştirak edən dəyişən həm də nəticəni saxlayan dəyişəndir və cari saxlanılan nəticə növbəti dövrün hesablanması üçün ilkin dəyər kimi istifadə olunur.
Rekursiv dövrədə, yekunlaşma şərti ödəndikdə, əvvəlki hesablamaların nəticələrini sona qədər qat-qat qaytarır. Dövrəni tamamlamaq üçün təkrarlama sayğacından istifadə edir. Əlbəttə ki, bir çox hallarda bir neçə dövrə qarışdırılır və xüsusi ehtiyaclardan asılı olaraq istifadə olunur. Uğurlu rekursiya üçün yadda saxlamaq lazımdır ki, rekursiya prosesində edilən hər bir çağırış hesablamanı sadələşdirməlidir. Rekursiya baza (əsas) qiymətə çatmaqla əldə edilir.
Məsələn, iki s₁ və s₂ sətirlərinin ən uzun ümumi ardıcıllığının uzunluğunu hesablamaq üçün alqoritm belə görünür:


Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]

Bu iterativ həlldir. Onun bu şəkildə kodlaşdırılmasının bir neçə səbəbi var:

• 
  İterasiya rekursiyadan daha sürətlidir.
  
• 
  Zaman və məkanın mürəkkəbliyini müəyyən etmək daha asandır.
  
• 
  Mənbə kodu qısa və təmizdir.
  

İlkin proqram koduna baxaraq, onun necə və niyə işlədiyini anlamaq olar, lakin bu məsələnin necə həll ediləcəyini görmək çətindir. Bununla belə, yuxarıda qeyd olunan iki yanaşma iki fərqli psevdokoda çevrilir. Biri iterasiyadan (aşağıdan yuxarı - Bottom-Up), digəri isə rekursiyadan (yuxarıdan aşağıya) istifadə edir. Sonuncu həm də yadda saxlama (memoization) üsulu kimi tanınır. Bununla belə, iki həll daha çox və ya daha az ekvivalentdir və digərinə çevrilə bilər.