Здравей,

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 е по-удобно да се напише итеративно (виж тук).