Рекурсия за 15 минути

Нека да си поставим цел - да съберем всички числа от 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 на конзолата.