Парадигмы программирования, 02 лекция (от 01 октября)

Материал из eSyr's wiki.

Версия 17:20, 1 октября 2009

• Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/pp02.ogg

void hello(int n)
{
if(n<1)return;
printf("Hello world\n");
hello(n-1);
}

Будет ли менее эффективно чем цикл? Цикл такой не развернется скорее всего. Если оптимизатор развернет хвостовую рекурсию, то будет парочка присваиваний при занятий стекового фрейма. Есть сомнения. Есть подозрения, что эффективность будет примерно одинаковая. Пока есть вывод, вы точно не увидите разницы в эффективности, принтф жрет намного больше.

Таким образом, заявления о том, что рекурсия неэффективна не всегда оправданы.

Это был пример простой рекурсии. Простая рекурсия --- функция вызвает сама себя в явном виде один раз. Здесь р еще и хвостовая, то есть р вызов последний в функции. Ее можно реализовать не тратя стек.

Другой пример, еопирование строки. Начинающий программист.

void strcpy(char* dest, const char* src)
{
int i;
i = 0;
while(src[i]!='\0')
{
	dest[i] = src[i];
	i++;
}
dest[i]='\0';
}
<pre>
Потом придет опытный сишник, и скажет "Гагага, у нас же есть арифметика указателей!" В си массивов как таковых практически нет, есть арифм указателей.
Хардкорный сишник напишет
while((*dest++=*src++)){};//(())to make the stupid compiler happy
Нет индекса.
Суперпозиции операций, пришедшие из ассемблера. Творцы си привыкли программировать на автокоде. Значение которое присваивают, остается в акумуляторе. Насколько особенность машины фон неймана влияет на япы и на мышление. Когда керниган томпсон и ричи придумывали язык си, они явно делали с прицелом на это. На пентиуме strcpy обычно реализуется как ассемблерная вставка. 
cinst char * src -- указываем на немодифицируюмую строку
char * const src -- немодифируем сам указатель

Теперь следующий момент. Придет человек который давно писал на си, а потом его посадили на лисп и догло долго не отпускали. что может совершенно случайно написать человек, кторый пишет на лиспе
<pre>
if((*dest=*src))
strcpy(dest+1, src+1);

возможно, но выглядит искуственно. Функция strdup дублирует строку. Класс реализация 2 прохода --- считаем длину, потом пробегаем-копируем. Два прохода, нехорошо.

char* strdup(const char* str)
{
	return do_strdup(str, 0);
}
//static функции недоступны вне модуля, используется для вспомогательных функций
static char* do_strdup(const char* str, int l)
{
	char* res;
	if(*str)
		res = do_strdup(str+1, l+1); //оставили заказ на память, на обратном ходе ей воспользуемся
	else
		res = malloc(l+1);
	res[l] = *str;
	return res; 
}

Чем оно может быть лучше? Да ничем. Но, это может быть удобно, если у нас поток ввода, а не строка. Там надо работать в один проход. Можем минимизировать вызовы функции маллок.

Есть функция gets(char* buffer) все знают, что ее нельзя использовать? Она читает до конца строки, и пишет буффер, но буффер ограничен. Естественно, хацкер поддсунет буффер оверфлоу. Способы разные бывают. Второкурсники делают список букв. 8 байт на одну букву с учетом выравнивания. А с учетом кванта маллока, который 32 байта.. Следующий уровень --- динам. массив. Иногда бывает даже новый маллок на каждую букву. Про реаллок не все знают, а в с++ ео и нет. Бывает стратеги удвоения выделяемой памяти. Но если сделать рекурсивные вызовы вглубь и так пока мы не найдем строки, сделать в конце маллок, потом распихать. Получится маллок ровно один. Сколько памяти тратится? В фрейме лок переменная, указатель, адрес фозврата, ebp. 16 байт на каждый вызов. Вроде бы как то многовато. Но стек то штука временная, освобождение легкое, в отличие от маллкоков. Если в стек не поместимся, можем нарваться на выделение новой страницы, но это не так страшно. В ткаой ситуации это может дать выигрыш в производительности, запросто. Упражнение Рекурсивная функция,заменяющая группы пробелов на один пробел. Рекурсивная реализация. На машине, а не на бумажке.

Накопительный параметр. Счетчик у нас уже был, а интересней когда параметр накапливает что нибудь серьезное. Как вариант --- переставить элементы списка в обратном порядке. Проще это делать не деструктивно, сделать новый сисок, хотя техника позволяет все сделать без единого маллока и без единого фри.

struct item
{
	int data;
	struct item* next;
};

Если применить лобовой способ. Первый вариант с двумя указателями. Если без них, то сосвесм плохо, потому что добавление в конец списка штука очень неприятная.

struct item* reverselist(struct item*list)
{
	return do_reverse_list(list, NULL);
}
static struct item* do_reverse_list(struct item* list, struct item* result)
{
if(!list)
	return result;
struct item* tmp = struct item*malloc(sizeof(struct item));//поьзуйтесь тайпдефом, не делайте как я
tmp = list->data;
tmp->next = result;
return do_reverse_list(list->next, tmp);
}

Опять хвостовая рекурсия. Это все были примеры простой рекурсии.

Параллельная рекурсия.

f()
{
g(..f(), ..f());
}

канонический пример --- обход дерева с, например, суммированием.

Взаимная рекурсия

f(...){...g()};
g(...){...f()};

Рекурсия высших порядков.

f(..){..f(..f(...))};

Простейший пример функция Аккремана. Если без головы делать, то вычисляем некоторые значения по многу раз, поэтому похорошему вводится кэширование уже вычисленного. Рекурсия высоких порядков встречается крайне редко. В реальной жизни однажды надо было стаскивать с трех серверов данные, и там была криптография с открытыми ключами, и все друг от друга зависело. Появилась комбинация взаимной и выского порядка.

Фанаты хаскеля утверждали, что применяли рекурсия третьего и четвертого порядка. В четвертый порядок я не верю, в третий --- с трудом, но это особенный люди. Четверты порядок, это как "печатая со скоростью 900 знаков в минуту, такая фигня получается".

Хрестоматийная задача. Сопоставление строки с образцом. * произвольная подстрока, втч пустая, ? -- лююой один символ. Было решение на сотню строк на джаве в жж, все было подсвечено, красиво, но совершенно непонятно. Имеет и рекурсивное простое решение, и циклическое несложное. Но решение на циклах как правило знают только те, кто умеет пользоваться рекурсией. Задача по сути своей рекурсивная. Циклическое решение слово в слово повторяет решение рекурсивное, только с явным запоминанием тех данных, которые при рекурсии остаются на стеке.

Итак, чисто рекурсивное решение. Сначала я это написал на лиспе. Сишное решение слово в слово повторяет то, что получилось на лиспе.

int match(const char* word, const char* pattern);
int starmatch(const char*word, const char* pattern)
{
	if(match(word, pattern)) return 1;
	if(!word) return 0;
	return starmatch(word+1, pattern); 
}

int match(const char* word, const char* pattern)
{
	switch(*pattern)
	{
		case '\0': return (*word == '\0');
		case '?': return (!*word)?0:match(word+1, pattern+1);
		case '*': return starmatch(word, pattern+1);
		default: return (*word != *pattern)?0:match(word+1, pattern+1);
	}
}

Некоторые программисты боятся рекурсии. Чтобы не боятся... Ну, язык си рекурсию не стимулирует ни разу, но он ее поддерживает. Если мы будем писать на си, использовать рекурсию мы не научимся. нужен более интересный язык, который будет стимулировать, поощрять использование рекурсии. Даже если лисп никогда не будете использовать на практике, его стоит изучить, чтобы уметь использовать рекурсию. С регекспом сопоставится так на халяву не получится, там потяжелее будет, хотя принцип абсолютно тот же.