|
Рекурсия дегеніміз – әдісте операторларды орындау барысында осы әдістің өзіне қайта жүгінуді орындайтын есептеу процесін ұйымдастыру тәсілі.
Рекурсиялық есептеулерді сипаттайтын классикалық мысалы - факториалды есептеу.
N! - есептеу керек болсын
N ! = 1·2· … ·(N-1)·N = (N - I) ! · N . (9)
Сонымен, N! есептеу үшін (N-1)! білу керек.
Өз кезегінде (N - 1) ! = 1·2· ...· (N - 2) !· (N - 1) , және т.б. 2 ! = 1 ! · 2 , 1 ! = 1.
N факториалын қарапайым FOR циклі арқылы есептеуге болады, мысалы:
pr = 1;
for (i=1; i<=N;i++) pr = pr*i ;
Цикл жұмысының нәтижесі pr айнымалысында жазылады.
Рекурсияны қолдану бір немесе бірнеше шартты циклдік операциялары бар күрделі есептерді оңай шешуге көмектеседі.
Сонымен қатар, шартты цикл денесі рекурсивті функцияға жазылады, ал функцияны қолдану бағдалама кодын қысқартады және оны түсінуді жеңілдетеді.
Рекурсивті функцияны қолданатын бағдарламаның мысалы ретінде диалог режімінде енгізілген бүтін санның факториалын есептеу бағдарламасын дайындаймыз.
Бағдарлама коды:
using System;
namespace ConsoleApplication1
{
class Program
{
static int fakt(int n)
{
int fu, k;
fu = n;
if (n != 1) { k = n - 1; fu = fu * fakt(k); }
return fu;
}
static void Main()
{
int a, n;
string buf;
Console.Write("n bytin canin engiziniz ");
buf = Console.ReadLine();
n = Convert.ToInt32(buf);
a = fakt(n);
Console.WriteLine("n! = {0}", a);
Console.WriteLine("Enter pernesin basiniz");
Console.ReadLine();
}
}
}
Бағдарлама жұмысы:
n bytin canin engiziniz 5
n! = 120
Enter pernesin basiniz
Көрсетілген бағдарлама кодында циклдар жоқ, бағдарлама алгоритмі жеңіл қабылданады: n айнымалының мәнін енгіземіз, факториалды есептейміз, монитор экранына нәтижені шығарамыз
Бағдарламаның орындалу үдерісінде fakt() рекурсивті функцияның жұмысын қарастырайық. Бағдарламаның жұмысы барысында 5 санын енгіздік деп есептейік.
5 саны үшін факториалды есептеу fakt(5)функциясы есептеледі. Бірақ fakt(5)функциясын есептеу үшін fakt(4) функциясын есептеу керек. Сондықтан fakt(5)функциясы уақытша тоқтатылады, оның параметрлері бағдарламалық стекке орналастырылады және 4 саны үшін факториалды есептеу fakt(4) функциясы іске қосылады.
Бірақ fakt(4)функциясын есептеу үшін fakt(3) функциясын есептеу керек. Сондықтан fakt(4)функциясы уақытша тоқтатылады, оның параметрлері бағдарламалық стекке орналастырылады және 3 саны үшін факториалды есептеу fakt(3) функциясы іске қосылады. Одан кейін стекке fakt(3), fakt(2) функцияларының параметрлері орналастырылады, тек содан кейін ғана fakt(1) функциясы есептеледі.
fakt(1) функциясының мәні болса, онда бағдарлама fakt(2) функциясының мәнін есептей алады. Ол үшін fakt(2) параметрлерін стектен шақыру керек және fakt(1) функциясының нәтижесін пайдаланып есептеу жұмысын жалғастыру керек. fakt(2) функциясының нәтижесін fakt(3) функциясын есептеу үшін қолдануға болады. Ол үшін fakt(3) параметрлерін стектен шақыру керек және fakt(2) функциясының нәтижесін пайдаланып есептеу жұмысын жалғастыру керек. Осыдан кейін fakt(4) және fakt(5) функциялары жоғарыда сипатталған үлгіде есептеледі.
fakt(5) есептелгеннен кейін оның нәтижесі a айнымалысына меншіктеледі және монитор экранына шығарылады.
Рекурсивті есептеулерді қолдану бағдарлама көрнектілігін арттырады, бірақ бағдарлама жұмысына әдеттегі циклді оператор көмегімен ұйымдастырылған бағдарламаларға қарағанда уақыт көбірек жұмсалады.
7.4-есеп. Келесі өрнекті есепте.
Мұнда N 5555 тең, бүтін тақ сан.
7.4-есептің шешімін екі жолмен қарастырайық. while шартты циклінің көмегімен және рекурсия арқылы.
Шартты цикл көмегімен есепті шешу алгоритмін шамасынан бастап шамасына дейін есептеу керек, әрбір циклда N 2-ге азайтылып отырады. Есептеу N>1 шарты орындалғанға дейін жүргізіледі.
Бағдарлама коды:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
double s, k, n;
n=5555;
k=1;
s = 1 / n;
while (n > 1)
{
n = n - 2;
s = 1 / (n + s);
}
Console.WriteLine("Natijesi = {0} ", s);
Console.WriteLine("Enter pernesin basiniz");
Console.ReadLine();
}
}
}
Бағдарлама жұмысының нәтижесі:
Natijesi = 0,761594155955765
Enter pernesin basiniz
Рекурсия алгоритмі өрнектің формуласымен анықталады, есептеу үшін есептеп алу керек, ары қарай дейін қайталанады.
Бағдарлама коды – 2:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static double rec(double k, double n)
{
double rez;
if (k< n) { k = k + 2; rez = (k - 2) + 1 / rec(k, n); }
else rez = n;
return rez;
}
static void Main()
{
double s, k, n;
n=5555;
k=1;
s = 1 / rec(k, n);
Console.WriteLine("Natijesi = {0} ", s);
Console.WriteLine("Enter pernesin basiniz ");
Console.ReadLine();
}
}
}
Бағдарлама жұмысының нәтижесі:
Natijesi = 0,761594155955765
Enter pernesin basiniz
Бағдарлама жұмысының нәтижесі бірдей.
Рекурсия қолданылған бағдарлама кодын түсіну жеңіл болып келеді.
Егер n айнымалысының мәнін ұлғайтсақ, мысалы n = 55555555, онда рекурсиясы бар бағдарламада стекті өзгертуді қажет етеді (рекурсия саны бағдарлама стегінің көлеміне байланысты), while циклді бағдарлама барлық ауқымдағы сандармен жұмыс істейді.
Бағдарламалық стекті пайдаланғандықтан бағдарламаның рекурсиямен жұмыс істеу уақыты циклдармен жұмыс істеу уақытынан көбірек (n шамасының мәні үлкен болғанда).
Достарыңызбен бөлісу: | 
