Именно поэтому программы, использующие динамическое выделение памяти, тоже «бажные», ведь памяти всегда может не хватить.

классическая проблема надежды на наличие ресурсов

Обычно в конце стека помещают страницу памяти, недоступную для чтения/записи. В итоге конец стека -> general protection fault -> завершение программы. По крайней мере, на x86 именно так выглядят стеки thread'ов.

По-хорошему malloc должен возвращать 0 при нехватке памяти и программа будет корректно обрабатывать эту ситуацию.

Узнать размер стэка - getrlimit.

У меня, по умолчанию, размер стэка - 10 Мб (RHEL 5). Сколько данных ты кладешь на стэк, что приходится задумываться о его размере?

По-хорошему рекурсию нужно ограничивать.

По-хорошему рекурсию нужно ограничивать.

если у рекурсии нет базиса, то это не рекурсия (а двойственная к ней корекурсия),- и смысла такая конструкция в неленивых языках не имеет

> У меня, по умолчанию, размер стэка - 10 Мб (RHEL 5). Сколько данных ты кладешь на стэк, что приходится задумываться о его размере?

Я могу не знать, сколько будет положено на стек. Если глубина рекурсии N, и это N зависит от пользовательского ввода, то злоумышленник может зафолтить программу, так ведь?

> По-хорошему рекурсию нужно ограничивать.

Как?

Вести от Капитана: нужно ставить жесткие лимиты на вещи которые могут вызвать перерасход памяти или экспоненциальный взрыв.

То есть не использовать рекурсию на уровне языка, а организовывать свой стек?

сам то понял, что сказал?

Например, ограничивать допустимую глубину вложенности.

> По-хорошему рекурсию нужно ограничивать.

Так как это сделать на уровне языка?

> То есть не использовать рекурсию на уровне языка, а организовывать свой стек?

можно передавать текущую глубину рекурсии как один из аргументов, с тем чтобы жестко ограничить глубину.

Вообще нужно все ограничивать, длину слов, глубину вложенности и т.п. Скажем, недавно пробегала ссылка на бесконечный zip-архив.

На уровне языка этого нет и не надо. Контролируй глубину вызовов сам, передавай макс глубину в вызове или сделай глобальную переменную для этого.

>если у рекурсии нет базиса, то это не рекурсия (а двойственная к ней корекурсия),- и смысла такая конструкция в неленивых языках не имеет
Вы всё про функциональщину?

>По-хорошему malloc должен возвращать 0 при нехватке памяти и программа будет корректно обрабатывать эту ситуацию.

Но стек может переполниться и без вызова malloc

>злоумышленник может зафолтить программу

А что, разве в этом есть что-то страшное? setjmp перед началом рекурсии и longjmp из обработчика разве не могут быть вариантом решения проблемы?

Example (писалось на коленке, проверялось только на работоспособность):

#include <signal.h>
#include <setjmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALTSTK_SIZE 16384
static jmp_buf r_exit;

static void sig11_handler(int sig)
{
	longjmp(r_exit, 1);
}

int recurse(int i)
{
	char dummy[6553600];
	(void)dummy;
	return i ? i * recurse(i - 1) : 1;
}

int main()
{
	stack_t ss;
	struct sigaction sa;
	ss.ss_sp = malloc(ALTSTK_SIZE);
	ss.ss_size = ALTSTK_SIZE;
	ss.ss_flags = 0;
	if (sigaltstack(&ss, NULL) == -1) {
		perror("sigaltstk");
		exit(EXIT_FAILURE);
	}
	memset(&sa, 0, sizeof(sa));
	sa.sa_handler = sig11_handler;
	sigemptyset(&sa.sa_mask);
	sa.sa_flags = SA_ONSTACK;
	sigaction(11, &sa, NULL);
	if (setjmp(r_exit) != 0) {
		printf("Recursion failed!\n");
	} else {
		int result = recurse(10);
		printf("Recursion result: %d\n", result);
	}
	return 0;
}

сам то понял, что сказал?

какое слово тебе непонятно?

Одно из решений это отказаться от рекурсии.

Вы всё про функциональщину?

я про вообще

ну мне например непонятна полностью терминология. которая в общем то не является общеизвестной терминологией. (хотя может в каком-то наборе работ она такая и есть)

Например я знаю, что такое присоединённое(двойственное) пространство (tangent space) в геометрии многообразий и физике.

я примерно помню, что понимается под коприсоединённым пространством.

однако я не могу отразить это на рекурсию и работу с ней. То же самое я уверен будет верно в отношении многих читающих.

Так же ИМХО использование усложнённой терминологии без принятия договорённости о ней (например ссылками на работы или дачей определений), а так же без необходимости показывает, то что человек не до конца разбирается в теме.

Что непонятно: базис рекурсии (тут сам виноват видел определения), твоё обозначение двойственной рекусии, твоё понимание корекурсии.

Что непонятно: базис рекурсии (тут сам виноват видел определения), твоё обозначение двойственной рекусии, твоё понимание корекурсии.

обозначение (определение) двойственности и понимание корекурсии - общепринятые:

http://en.wikipedia.org/wiki/Corecursion

In computer science, corecursion is a type of operation that is dual to recursion

двойственность понимается категориально

базис рекурсии определяет точку выхода из неё. термин также общепринятый:

http://en.wikipedia.org/wiki/Recursive_definition

Most recursive definition have three foundations: a base case (basis), an inductive clause, and an extremal clause.

...recursive definition must always have base cases

корекурсивное определение не имеет точки выхода, потому и работа с ним имеет смысл только в ленивых языках, поддерживающих бесконечные структуры данных. ещё претензии?

> обозначение (определение) двойственности и понимание корекурсии - общепринятые:

какое из определений двойственности общепринятое: ^_^

http://en.wikipedia.org/wiki/Duality_(mathematics)

ещё претензии?

По скольку ЛОР не является научным тематическим журналом, то до начала реального спора где есть необходимость ссылаться на источники, или использовать терминологию не допускающую двусмысленности, к тому же если ты уверен, что понимаешь правильно и те кто с тобой общаются поймут это так же как и ты, то ИМХО лучше избегать подобной терминологии :)

переводя на норм язык, а своими словами можешь описать? :)

какое из определений двойственности общепринятое: ^_^

все. уточнение зависит от контекста, который у тебя есть. даже википедийное определение корекурсии достаточно пространно расписывает этот момент

использовать терминологию не допускающую двусмысленности

контекст исключает двусмысленность. если ты можешь предложить альтернативную трактовку двойственности в контексте корекурсии, буду рад почитать

переводя на норм язык, а своими словами можешь описать? :)

ещё раз - что именно тебе непонятно? корекурсивное определение множества натуральных чисел? какой-то термин? как это использовать?

те кто с тобой общаются поймут это так же как и ты

у тебя, кстати, bind на аватаре; да, я предполагаю, что ты как минимум знаешь, что такое монада и комонада

> даже википедийное определение корекурсии достаточно пространно расписывает этот момент

кстати оно почти никакое, и нет ссылки на работы где это описано, что грустно видеть.

контекст исключает двусмысленность.

может быть.

у тебя, кстати, bind на аватаре; да, я предполагаю, что ты как минимум знаешь, что такое монада и комонада

что такое монада я знаю, но разбираюсь не так хорошо как хотелосьбы

а приставку ко- в computer science я пока не осознаю :)

> корекурсивное определение не имеет точки выхода, потому и работа с ним имеет смысл только в ленивых языках

а в Scheme есть delay, а в CL этот delay легко реализовать. в них имеет смысл? =)

а в Scheme есть delay, а в CL этот delay легко реализовать. в них имеет смысл? =)

ленивый eDSL в строгом языке - почему бы и нет?

govno (26.04.2010 14:26:36)

отличный никнейм.

а приставку ко- в computer science я пока не осознаю :)

http://en.wikipedia.org/wiki/Duality_(mathematics)#Dual_categories

http://www.amazon.com/Categories-Computer-Science-Cambridge-Texts/dp/0521422264

боюсь мне пока не попути с теорией категорий, ибо и без того есть дофига чего учить :) да и «догоро(с)»

что ж, личное дело каждого

Используй хвостовую рекурсию и компилируй gcc с -Ox, где x>=1

То-есть gcc оптимизирует хвостовую рекурсию? Для языка C? А пруф будет?
Пока обязательную оптимизацию хвостовой рекурсии я видел только в OCaml и Scheme.

См. -foptimize-sibling-calls

понял

> То-есть gcc оптимизирует хвостовую рекурсию? Для языка C?

Да

А пруф будет?

Вы спросили - вам ответили (коротко, конкретно и по существу). Информация - из стандартной документации. Вам нужны «пруфы» - ищите. Я «доказывать» что-либо неграмонтным студентам не собираюсь.

забыть о рекурсивных вызовах нафиг, пытаться преобразовать рекурсию к хвостовой и, далее, к итерационному алгоритму, например

> забыть о рекурсивных вызовах нафиг, пытаться преобразовать рекурсию к хвостовой и, далее, к итерационному алгоритму

Главное - школу не прогуливать.