Рекурсия және итерация

Презентация қосу

Рекурсия және
итерация
Тексерген:Дошева Гүлжихан
Орындаған:Елтаев Арынғазы,Турлан Ляззат
• Рекурсия - бұл бағдарлама (немесе функция) өзін тікелей немесе
басқа бағдарламалардан (функциялардан) шақыратын
мәліметтерді өңдеуді ұйымдастыру тәсілі.
• Функция рекурсивті деп аталады , егер оны өңдеу кезінде ол
тікелей немесе жанама түрде басқа функцияларға қоңырауларды
тізбектеу арқылы қайта шақырылса.
• Итерация - бұл кейбір әрекеттерді бағдарламалардың
(функциялардың) рекурсивті шақыруларына соқтырмай бірнеше
рет қайталайтын мәліметтерді өңдеуді ұйымдастыру тәсілі.
• Теорема. Рекурсивті формада жүзеге асырылған ерікті алгоритмді қайталанатын түрде
және керісінше қайта жазуға болады.
• Әрі қарай, біз цикл операторларының және рекурсивті тәсілдің көмегімен жүзеге
асырылатын элементар функциялар жиынтығын қарастырамыз. Кез-келген
бағдарламалау тілінде рекурсивті функцияларды жазбас бұрын, ереже бойынша,
функцияларды есептеу әдісін анықтайтын рекурсивті қатынасты жазу керек .
Қайталану қатынасы кем дегенде екі шартты қамтуы керек:

• I) рекурсияның жалғасу шарты (рекурсия қадамы);

• II) рекурсияның аяқталу шарты.

• Біз рекурсияны функцияны шақыру арқылы жүзеге асырамыз. Бұл жағдайда
функция денесінде алдымен рекурсияның жалғасу шарты тексерілуі керек. Егер бұл
дұрыс болса, онда функциясынан шығыңыз. Әйтпесе, біз рекурсивті қадам жасаймыз.
• Функциясының итерациялық нұсқасы цикл операторының көмегімен жүзеге асыруға болады
арналған .
• 1. Санның факторлық мәні. Теріс емес бүтін факторлық N 1-ден барлық табиғи сандар өнім
болып табылады N және белгіленеді N !. Егер f ( n ) = n ! Болса, онда қайталану қатынасы орын
алады:

• Бірінші теңдік рекурсиялық қадамды - f ( n ) -ді f ( n - 1) арқылы есептеу әдісін сипаттайды .
Екінші теңдік функцияны бағалауды қашан тоқтататынын көрсетеді. Егер сіз оны көрсетпесеңіз,
функция шексіз жұмыс істейді.

• Мысалы, f (3) -ды келесідей есептеуге болады:

• f (3) = 3 f (2) = 3 2 f (1) = 3 2 1 f (0) = 3 2 1 1 = 6

•F(n) есептеу кезінде n рекурсивті шақырулар жасалуы керек .
рекурсивті енгізу циклдық енгізу
int f ( int n) int f ( int n)
{ {
if (! n) return 1; int i, res = 1;
n * f (n - 1) қайтару ; үшін (i = 1; i <= n; i ++) res = res * i;
} қайтару ;
}

Ілгекті іске асырудың идеясы цикл операторын қолдана отырып, санның факториалын тікелей есептеу:

f ( n ) = 1 · 2 · 3 · ... · n
• 2. Сызықтық уақыттағы санның дәрежесі. F ( a , n ) = a n санының
қуатын сызықтық (O ( n )) уақыт бағасымен есептеп шығаруды келесі
қайталану қатынасы арқылы анықтауға болады:

рекурсивті енгізу циклдық енгізу
int f ( int a, int n) int f ( int a, int n)
{ {
if (! n) return 1; int i, res = 1;
a * f (a, n - 1) қайтару ; үшін (i = 0; i } қайтару ;
}

Итерациялық нұсқада a · a ·… · a ( n фактор а ) көбейтіндісін есептеу
жеткілікті .
• 3. Логарифмдік уақыттағы санның дәрежесі. F ( a , n ) = a n санының қуатын
есептеу О уақыттық бағамымен (журнал 2 n ) келесідей анықталады:

• Мысалы, оныншы билікке көтерілу келесідей болуы мүмкін:

• Квадрат бір көбейтуге тең болғандықтан , 10- ды есептеу үшін 4 көбейту
жеткілікті.
рекурсивті енгізу циклдық енгізу
int f (int a, int n) int f ( int a, int n)
{ {
if (! n) return 1; int res = 1;
егер (n & 1) a * f (a * a, n / 2) мәнін қайтарса ; ал (n> 0)
қайтару f (a * a, n / 2); {
} егер (n & 1) res * = a;
n >> = 1; a * = a;
}
қайтару ;
}
• 4. Санның цифрларының қосындысы. N натурал санының цифрларының қосындысын
келесідей анықталған f ( n ) функциясы арқылы табуға болады:

• Рекурсияны жалғастырудың шарты: санның цифрларының қосындысы соңғы цифрына
және соңғы цифры жоқ сан цифрларының қосындысына тең (сан 10-ға бөлінеді).

• Рекурсияның аяқталу шарты: Егер сан 0-ге тең болса, онда оның цифрларының
қосындысы 0-ге тең.

• Мысалы, 234 сандарының қосындысы келесідей есептеледі:

• f (234) = 4 + f (23) = 4 + 3 + f (2) = 4 + 3 + 2 + f (0) = 4 + 3 + 2 + 0 = 9
НАЗАРЛАРЫҢЫЗҒА
РАҚМЕТ!!!

Ұқсас жұмыстар

ЕСЕПТЕУДІҢ АЛГОРИТМДІК ШЕШІМІ АЛГОРИТМДІК КҮРДЕЛІКТІ ТАЛДАУ

ЭКОНОМИКАЛЫҚ ЕСЕПТЕРДІ СИМПЛЕКС ӘДІСПЕН ШЕШУ

For циклдық операторы

ГАЛАКТИКА ФОРМАСЫН СИПАТТАЙТЫН ҮШ ӨЛШЕМДІ БЕЙНЕЛЕУ

Теңдеулер жүйесін шешудің Зейдель әдісі

Функциялар мен процедуралар

Тьюринг машинасы. Алан Мэтисон Тьюринг

Программаны жасақтаудың негізгі кезеңдері

Шешілмейтін алгоритмдер туралы түсінік

Алгоритмдер туралы түсінік

Пәндер