+2 əjdaha
1. Bir dəfə bu başlığı sırf aşağıdakı şəkildə doldurmuşdum, lakin entry başlıq haqda kifayət qədər məlumat verməməsi səbəb göstərilərək silindi:--spoiler--
(bax: recursion)
--spoiler--
Yəqin silən mod söhbət nədən gedir tutmadı, ya da ki zarafatın başlığa uyğun olması yenə də sözlük qaydalarında istisna yaratmırdı-*
"recur" (yenidən baş vermək) feilindən törəyən isim, xüsusilə, riyaziyyat və kompüter elmlərində geniş istifadə olunan konsept. Bir funksiyanın tərifində o funksiyanın özünün iştirak etməsi ilə yaranır. Məntiqən bir şeyin tərifində həmin şeyin özünün iştirak etməsi mənasız səslənə bilər. Məsələn: "dürüst insan özünə dürüst deyən insandır" tərifində "dürüst insan" qavramını izah edərkən elə o ifadənin özündən istifadə edilməsi "dürüst insan" anlayışının tamamilə havada qalmasına səbəb olur. Bəs özü-özünü tərifləndirən rekursiv funksiyalar necə mənalı ola bilir? Cavab funksiyanın tərifində həmçinin "base case" (əsas hal?) adlanan varsayımın iştirakıdır. Misal üçün, bir çoxumuzun , bəlkə də, eşitdiyi Fibonacci sırasında n-ci ədədi təyin edən funksiyaya baxaq:
F(n) := F(n - 1) + F(n - 2), n natural ədəddir və n >= 3.
Yəni n-ci Fibonacci ədədi özündən əvvəlki və ondan da əvvəlki ədədin cəminə bərabərdir. Deyək ki, 3-ci ədədi axtarırıq, bu zaman:
F(3) = F(2) + F(1). Məsələ odur ki, 2-ci və 1-ci yerdə duran ədədləri bilmədiyimiz üçün 3-cü yerdə duran ədədin də mənası olmur. Bu səbəbdən 1-ci və 2-ci ədədlərə base case olaraq default qiymətlər veririk. Fibonacci sırasında isə bu ədədlərin ikisinin də 1 olması qəbul olunub.
F(1) = 1
F(2) = 1
Bu zaman yerdə qalan ədədləri asanlıqa hesablaya bilərik:
F(3) = F(2) + F(1) = 1 1 = 2
F(4) = F(3) + F(2) = 2 1 = 3
F(5) = F(4) + F(3) = 2 3 = 5
F(6) = F(5) + F(4) = 5 3 = 8
...
F(i) = F(i - 1) + F(i - 2).
Deməli, Fibonacci sırasında n-ci ədədi müəyyən edən rekursiv funksiyanın tam tərifi aşağıdakı kimi olur:
F(1) = 1
F(2) = 1
F(n) := F(n -1) + F(n - 2), n natural əddədir və n >= 3.
Bundan əlavı faktorial funskiyası da rekursiv şəkildə təyin olunur:
0! = 1 (base case)
n! = n (n - 1)! , n tam ədəddir və n >= 0 (recursive step).
Proqramlaşdırmada isə, özü-özünü "call" edən funksiyalar recursion yaradır. Base case təyin edilmədikdə isə memory problemlərinə görə proqram kəsilir. Misal üçün, base case olmadıqda və ya düzgün yazılmadıqda Java-da "stackOverFlow Exception" şəklində xəta mesajı ilə proqram execution processinin sonuna çatmadan kəsilir.