Софтуерно Инженерство
Loading...
+ Нов въпрос
enevlogiev avatar enevlogiev 1169 Точки

[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 4428 Точки

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

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

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

1
iordan_93 avatar iordan_93 SoftUni Team 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 1169 Точки

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

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

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

0
Filkolev avatar Filkolev 4428 Точки

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

0
iordan_93 avatar iordan_93 SoftUni Team Trainer 407 Точки

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

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

1
19/05/2015 19:25:36