Нека да си поставим цел - да съберем всички числа от 1 до n. Ако n е 4, то тогава събиането би било - 4 + 3 + 2 + 1. До тук в канала сме обсъждали методи и функции и цикли.
Лесно бихме могли да излезем със заклчението, че можем да постигнем това като разпишем следния метод;
public static int SumNumsN(int n)
{
int sum = 0;
for (int i = n; i >= 1; i--)
{
sum += i;
}
return sum;
}
Как бихме могли да решим същия проблем с рекурсия? Днес ще си говорим за ......, което още в началото трябва да отбележим, че е поне два пъти по-бавно от итерацията и че, ако н е голямо число, то това не изменно ще доведе до препълване на стака.
Нека да видим как бихме могли да го имплементираме и да видим и защо е толкова бавно.
Казваме на нещо, че е рекурсия, ако една функция се вика директно или индиректно сама себе си. Рекурсивната функция се състои от две части:
- дъно на рекурсията (тоест кога ще спре да се извиква ) и извикването на самата функция в себе си.
Ето как бихме могли да дефинираме дъното на една рекурсивна функция:
public static int SumNums(int n)
{
if (n == 1)
{
return 1;
}
}
До тук добре, но къде е частта, която я прави рекурсивна? Нека добавим реда, който ще накара функцията да вика сама себе си:
public static int SumNums(int n)
{
if (n == 1)
{
return 1;
}
return n + SumNums(n - 1);
}
Интересният момент тук е, че последния ред ни дава ясно да разберем, че стигайки до него функцията ще се викне отново, само че параметърът ще бууде n - 1.
Ето как би работило:
static void Main(string[] args)
{
Console.WriteLine(SumNumsN(4));
}
public static int SumNums(int n)
{
if (n == 1)
{
return 1;
}
return n + SumNums(n - 1);
}
Викаме функцията с параметър n = 4. То влиза във функцията и вижда, че н не е едно и се самоизвиква. Имаме второ извикване, което отново влиза в себе си като н-1 т.е. 3, после 2 и после 1. Сега обаче стигнахме дъното на рекурсията, която връща стойност 1
Това означва, че започваме по обратния път с стака да заместваме стойностите и накрая стигаме до 4 +3 + 2 + 1. Което се връща обратно в мейн метода и ни принтира резултатът 10 на конзолата.
23 авг 2019
