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

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

• Аудиозапись: 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);
}

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

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

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

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

void strcpy(char* dest, const char* src)
{
int i;
i = 0;
while(src[i]!='\0')
{
	dest[i] = src[i];
	i++;
}
dest[i]='\0';
}

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

Теперь следующий момент. Придет человек который давно писал на си, а потом его посадили на лисп и долго не отпускали. Что может совершенно случайно написать человек, который пишет на лиспе:

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; 
}

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

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

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

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(...))};

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

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

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

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

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);
	}
}

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