Rekursiya
Bir çox mühüm anlayışlardan biri, alqoritmlər nəzəriyyəsində istifadə olunan rekursiyadır. Qeyri-formal olaraq, rekursiyanı obyektin təsvirində özünü istifadə etməsi kimi müəyyən etmək olar. Əgər söhbət prosedurdan gedirsə, icra prosesində bu prosedur birbaşa və ya dolayı yolla (başqa prosedurlar vasitəsilə) özünü çağırır.
Rekursiya alqoritmlərin qurulmasında çox "güclü" bir üsuldur, lakin bəzi təhlükələri də özündə gizlədir. Məsələn, diqqətsiz yazılmış rekursiv prosedur sonsuz rekursiyaya girə bilər, yəni heç vaxt icrasını bitirməz (əslində icra stack dolması ilə bitəcək).
Rekursiya dolayı ola biləcəyi üçün (prosedur başqa prosedurlar vasitəsilə özünü çağırır), konkret bir prosedurun rekursiv olub-olmamasını müəyyən etmək məsələsi kifayət qədər çətin ola bilər.
n prosedurdan P[1], P[2], ..., P[n] ibarət proqramı nəzərdən keçirək. Hər bir prosedur üçün hansı prosedurların çağırıla biləcəyi məlumdur. P proseduru potensial rekursiv adlanır, əgər elə bir prosedurlar ardıcıllığı Q[0], Q[1], ..., Q[k] varsa ki, Q[0] = Q[k] = P və i = 1 ... k üçün Q[i-1] proseduru Q[i] prosedurunu çağıra bilər.
Hər bir verilmiş prosedur üçün onun potensial rekursiv olub-olmadığını müəyyən edən bir proqram yazmaq lazımdır.
Giriş məlumatları
Birinci sətir proqramda olan prosedurların sayı n (1 ≤ n ≤ 100) ilə başlayır. Sonra prosedurları təsvir edən n blok gəlir. Bloklar bir-birindən hər biri 5 simvoldan "*" (ulduz) ibarət sətirlərlə ayrılır.
Prosedurun təsviri onun identifikatorunu ehtiva edən sətirlə başlayır, bu yalnız kiçik latın hərfləri və rəqəmlərdən ibarətdir. İdentifikator həm hərflə, həm də rəqəmlə başlaya bilər. İdentifikatorun uzunluğu 1-dən 100-ə qədər simvoldur. Sonra prosedurun çağıra biləcəyi prosedurların sayını göstərən k (k ≤ n) ədədini ehtiva edən sətir gəlir. Növbəti k sətir bu prosedurların identifikatorlarını ehtiva edir - hər sətirdə bir identifikator.
Fərqli prosedurların fərqli identifikatorları var. Bu halda heç bir prosedur girişdə təsvir olunmayan proseduru çağıra bilməz.
Çıxış məlumatları
Girişdə mövcud olan hər bir prosedur üçün, girişdə göstərildiyi ardıcıllıqla, ayrı-ayrı sətirdə prosedurun adını, sonra iki nöqtə, boşluq, sonra YES sözü, əgər prosedur potensial rekursivdirsə, əks halda NO sözünü çıxış edin.