Loading...
+ Нов въпрос
enevlogiev avatar enevlogiev 1168 Точки

[Technical issue] Тail recursion C# ??

Първо историята накратко. Решавам задачките от лаба с алгоритмите по Advanced C#. Четвърта задача ми е най-интересна и почвам от нея. Понеже искам да се помъча повече, реших да си я мисля рекурсивно, като просто обяснението, което е дадено в условието на задачата, го имплементирах в един метод. Нямам проблеми, задачката си върви - ето код на който му е интересно.

Сега вече следва и същинското питане. Имам ReSharper, който ми обяснява, че това цялото може да се напише с while цикъл. Добре, няма проблеми, обаче аз не искам, кефа си се на задачката така. Самото обяснение е "Tail recursion can be implemented with a while loop". Става ми интересно какво точно е Tail рекурсия, обаче според този пост, в C# такъв тип рекурсия няма.

Някой може ли да разясни малко повече, на ReSharper ли да вярвам, или на StackOverflow.

Ps. в уикипедия също не се споменава за Tail рекурсия в C#, в F# има. Не че някога съм виждал F#.

Ps2. всякакви критики по кода се приемат без обиди, даже ще се радвам да ми посочите къде да подобрявам, рекурсия тренирам от скоро : )

Тагове:
0
C# Advanced 18/05/2015 23:17:17
Filkolev avatar Filkolev 4482 Точки

Правилото е: ако можеш да приложиш нещо линейно като обикновен цикъл вместо рекурсия - не ползвай рекурсия. В случая Resharper ти дава добър съвет (с малки изключения са му добри съветите).

Това, което пише в поста, който си споделил, е, че в C# JIT компилатора не оптимизира такъв тип рекурсия. В процеса на компилация се правят страшно много оптимизации. Например ако компилатора види, че викаш метод, който не променя никакви данни и не връща стойност, или че не ползваш върнатата стойност - тоя метод въобще няма да се извика. Та въпросът на автора там е "Защо компилатора на C# не оптимизира тая рекурсия", т.е. защо не я заменя с цикъл. 

За да упражниш рекурсия по-скоро трябва да се насочиш към задачи, които я изискват - обхождане на дървета и графи да речем. Не е много правилно насила да я ползваш на място, в което не е нужна; дори само за експеримента да е - по-добре потърси задача за претърсван или нещо подобно.

1
iordan_93 avatar iordan_93 Trainer 407 Точки

Здравей,

Tail recursion е, в най-общи линии, рекурсия, която викаш в самия край ("на опашката") на един цикъл или един метод (на последния ред). Тя е много често срещано явление във функционалните езици за програмиране (F#, Scala, Haskell...). Причината е, че в тези езици няма цикли. Long story short, такава е парадигмата на функционалните езици, че for-циклите нямат място в нея. Затова обаче има tail recursion. Та, tail recursion е вид рекурсия, подобна на циклите, които познаваме, но не е цикъл.

Пример:

int TailRecursiveMethod(int param)
{
    // Some code here
    return TailRecursiveMethod(param - 1);
}

Там, където е коментара, можеш да имаш какъв да е код. Виж как методът се извиква рекурсивно накрая. Сравни с този случай, където рекурсията е нормална:

int RecursiveMethod(int param)
{
    // Some code here
    int result = RecursiveMethod(param - 1);
    // Some other code here
}

Каква е разликата с нормалната рекурсия?

Бележка - call stack: Когато викаш един метод, C# компилаторът запомня на кое място в кода си го извикал. Това става с помощта на така наречения call stack. Той работи така: когато викнеш някакъв метод, в call stack-a се създава запис за мястото, откъдето е извикан. Когато този метод return-не, контролът (изпълнението на програмата) се връща на записаното място (все едно да си отбележиш в една книга докъде си стигнал и да продължиш по-късно оттам).

Рекурсията нормално създава нов запис и веднага след това изтрива един запис (демек, хаби малко повече място по stack-a, който е ограничен). Tail рекурсията преизползва едно и също място в call stack-a. На ниско ниво това означава по-бърз код (спестяват се едни времена и едни проверки).

Защо го няма това в C#? Две основни причини:

1) C# поддържа елементи от функционалното програмиране, но по никакъв начин не му е това основната парадигма. Накратко, има си цикли :D, може да мине и без тази оптимизация

2) Дълга история е защо, но да се направи тази оптимизация изобщо не е тривиална задача. Компилаторът трябва освен да оптимизира кода, да работи и бързо. Та, проблем е да се имплементира това нещо в език като C# - има доста проблеми, които не са нито очевидни, нито лесни за оправяне. В поста (и реферираните от него други постове) са разгледани тези проблеми в детайли, ако ти се занимава :)

Колкото до кода, по идея всяко нещо, което може да се направи с рекурсия, може да се направи и без рекурсия (итеративно) и обратно. В случая binary search е по-удобно да се напише итеративно (виж тук).

6
19/05/2015 03:08:48
enevlogiev avatar enevlogiev 1168 Точки

Аз бърках Tail Call с Таil Recursion. Значи ришарпъра не ме лъже, просто аз не го разбирам правилно : D Голяма изненада.

Благодаря за отговора. Ако на някого му е станало интересно и иска нещо допълнително - тук има много хубаво обяснение, като за хора с бекграунд C#. Java и подобни езици.

А до теб и до Фил: не се притеснявайте, няма да почна да пиша всичко рекурсивно (една причина е защото най-вероятно не мога : ) ) . Просто обичам да разцъквам някакви неща и да видя къде ще се строшат.

0
Filkolev avatar Filkolev 4482 Точки

Рекурсията си има приложения, просто трябва да се ползва по-пестеливо. Докато си писал задачата предполагам на някакъв етап ти се е наложило да дебъгваш и подозирам, че поне в първия момент ти е било малко трудно да се ориентираш какво се случва в дебъгера. Винаги е полезно да разцъкваш :)

0
iordan_93 avatar iordan_93 Trainer 407 Точки

За да я има рекурсията, значи има причина :). Факт е, че някои задачи се решават много по-лесно с нея. Особено интуитивно се прилага за структури от данни, в които отделните "парчета данни" са свързани по малко по-сложен начин - графи и дървета.

А това "Просто обичам да разцъквам някакви неща и да видя къде ще се строшат." е не само полезно, а е най-добрият и ефективен начин да се научиш :). При мен винаги работи :).

1
19/05/2015 19:25:36
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.