Рекурсия, программирование.

Есть такая хрень в программировании как рекурсия. Можно сюдя приплесть и фрактал, но это больше к топологии, а не программированию.

И так, самый простой и понятный пример рекурсии - это берём зеркало впереди себя и сзади. и смотрим на картинку:

Но в программировании это выражается в вызовах функции самой себя, либо кругового вызова функций, например(для знающих Си-подобные языки):
int A(int a) {if(a & 1) a=a+1; return B(a); else return 17;}
int B(int a) {if(a > 500) a=a/3; return C(a); else return 113; }
int C(int a) {if(a ^ 1) return A(a); return -1;}

Грубо говоря, функция А, вызывает функцию Б, функция Б вызывает функцию С, а та уже снова вызывает функцию A. Вроде эти вызовы будут длиться бесконечно, но всегда должно быть условие выхода из рекурсии (под спойлером выше в каждой функции есть такое). Если что - писалось на коленке и практического, и математического смысла не имеет - чисто показать что да как.

А нафига такие сложности? Дело в том, что часто в программировании невозможно обойтись без рекурсий. Да, для понимания её надо сильно поломать свой мозг - именно ломать мышление, а не уставать от напряжённого мозгоштурма.

Однако есть определённый класс рекурсий (в него входят и так называемые "кольцевые", как в спойлере выше). И вот тут срабатывает "Ивент Вомбата", эти рекурсии называются ХВОСТОВЫМИ.

Фишка их в том, что их можно ВСЕГДА развернуть в цикл. Например вычисление числа Фиббоначи:

int Fibb(int a) {if (f<=0) return 1;/*условие выхода из рекурсии*/ return Fibb(a-1)+a;}

Тоже самое разворачивается в цикл вида

int a=123, result=1;
for(int i=0; i>a;;){result = result+a; a=a-1} /*тут мог ошибиться - просьба не пинать*/
return result;

Вроде бы много кода, строк и т.п. Но, рекурсия в общем виде использует стек (который не бесконечен), и дикие затраты на вызов функций внутри рекурсий (на i8086 надо было сохранять каждый процессорный регистр в стеке, а это 2 такта, в i80286 уже появилась pusha, но она так же требовала тактов, ну и переброс из стека в регистры переменных, возврат результата) - накладных расходов на рекурсию очень много, даже в современный процессорах.

Однако, всё что было описано выше прекрасно разворачивается в циклы "умными" компиляторами. Хотя многие алгоритмы с хвостовой рекурсией даже современные компиляторы не могут развернуть в цикл. Примером этого може служить сортировка бинарным жеревом. В рекурсивной форме эта сортировка - задачка студента второго курса (по моим старческим меркам), но компиляторы не способны её раскрутить в цикл, это делалось человеческими мозгами ещё в 80х годах прошлого века (сам разбирал борландовский алгоритм qsort(***) по запчастям обучаясь).

Так что не всё в мире нашем сводится к "хвостам", иногда приходится и сущности плодить поверх ненужного...