бесконечная рекурсия: почему нет ограничений? - C/C++

Здравствуйте, varnie, Вы писали:

V>Здравствуйте, merk

V>хмм, а как тогда объяснить вот это:

V>у меня есть класс примерно как класс Test выше (реализующий семантику "функция"), один в один с таким же механизмом предотвращения выполнения ф-ции на глубину превышающую MAX_EXECUTION_DEPTH (перед и после вызова самого исполнения ф-ции я воткнул printf("counter=%d\n", counter)

.
V>

V>void CFunction::invoke() { 
V>    // printf("exec");
    
V>    static std::size_t counter = 0;
    
V>    if (_pStmtPtr != NULL) {
V>       if (counter++ < MAX_FUNCTION_EXECUTION_DEPTH){
V>          printf("counter=%d\n", counter);
V>        _pStmtPtr->exec();
V>         printf("counter=%d\n", counter);
V>        --counter;
V>       }else{
V>          throw CRunTimeException(NULL, "stack depth exceeded");
V>       }
        
V>    }
V>}
V>

V>и интерпретируется у меня к примеру вот такой код на моем языке:
V>test1.src
V>

V>bool test(){}          //для этой ф-ции заведется объект класса CFunction
V>void C(int i){ C(); }  //для этой еще один

V>{ //точка входа        //и для этой.
V>  C(1);
V>}
V>

V>для этого случая я вижу:
V>

V>counter=1
V>counter=2
V>counter=3
V>counter=4
V>counter=5
V>counter=6
V>...
V>counter=20
V>"stack depth exceeded" //сработала моя проверка на глубину больше 20. все верно.

V>далее, интерпретируемый сорец на своем языке я заменяю на:
V>test2.src
V>

V>bool test(){}
V>void C(int i){ test(); test(); test(); test(); test(); test(); test(); test(); test(); test();

V>{ //точка входа
V>  C(1);
V>}
V>

V>вывод:
V>

V>counter=1
V>counter=2
V>counter=2
V>counter=1

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

V>если взять на вооружение что вы сказали что статич. переменная в методе класса одна на все объекты этого класса, тогда я не догоняю, как тогда понять результаты выше?
V>спасибо за прояснение.

зачем вам переменная на класс, если у вас должна быть своя переменная на каждую функцию.
если ваша invoke просто типо вызов произвольной функции в каком-то интерпретаторе, то вы считаете общую глубину вызовов в вашем интерпретаторе...или я чета не понял.
у меня сейчас ребенок на руках, нет времени долго всматриваться в текст.
смогу точней ответить только позже.

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

void U() { print(21);     }
void T(){ print(20); U(); }
void S(){ print(19); T(); }
void R(){ print(18); S(); }
void Q(){ print(17); R(); }
void P(){ print(16); Q(); }
void O(){ print(15); P(); }
void N(){ print(14); O(); }
void M(){ print(13); N(); }
void L(){ print(12); M(); }
void K(){ print(11); L(); }
void J(){ print(10); K(); }
void I(){ print(9); J(); }
void H(){ print(8); I(); }
void G(){ print(7); H(); }
void F(){ print(6); G(); }
void E(){ print(5); F(); }
void D(){ print(4); E(); }
void C(){ print(3); D(); }
void B(){ print(2); C(); }
void A(){ print(1); B(); }

{ 
    A();  //точка входа
}

то мы также получим сообщение что "stack depth exceeded", хотя никакой рекурсии, очевидно, и нет.
значит подходом с статик переменной мою задачу не решить и надо заводить доп. член на кажд ф-цию для хранения числа её вызовов. при вызове ф-ции мы инкрементируем этот счетчик, при выходе из нее -- декрементируем. если привышаем, скажем, 20, кидаем исключение как в коде выше. сейчас попробую. спасибо за помощь выше.

Здравствуйте, varnie, Вы писали:

V>верно, я ошибся в своем предположении выше. у нас считается именно суммарное кол-во вызовов ф-ций. и это не то что мне нужно. также я понял что статич переменная одна на все инстанциированные объекты этого класса.
V>скажем, если проинтерпретировать
V>

V>void U() { print(21);     }
V>void T(){ print(20); U(); }
V>void S(){ print(19); T(); }
V>void R(){ print(18); S(); }
V>void Q(){ print(17); R(); }
V>void P(){ print(16); Q(); }
V>void O(){ print(15); P(); }
V>void N(){ print(14); O(); }
V>void M(){ print(13); N(); }
V>void L(){ print(12); M(); }
V>void K(){ print(11); L(); }
V>void J(){ print(10); K(); }
V>void I(){ print(9); J(); }
V>void H(){ print(8); I(); }
V>void G(){ print(7); H(); }
V>void F(){ print(6); G(); }
V>void E(){ print(5); F(); }
V>void D(){ print(4); E(); }
V>void C(){ print(3); D(); }
V>void B(){ print(2); C(); }
V>void A(){ print(1); B(); }

V>{ 
V>    A();  //точка входа
V>}
V>

V>void U() { print(21);     }
V>void T(){ print(20); U(); }
V>void S(){ print(19); T(); }
V>void R(){ print(18); S(); }
V>void Q(){ print(17); R(); }
V>void P(){ print(16); Q(); }
V>void O(){ print(15); P(); }
V>void N(){ print(14); O(); }
V>void M(){ print(13); N(); }
V>void L(){ print(12); M(); }
V>void K(){ print(11); L(); }
V>void J(){ print(10); K(); }
V>void I(){ print(9); J(); }
V>void H(){ print(8); I(); }
V>void G(){ print(7); H(); }
V>void F(){ print(6); G(); }
V>void E(){ print(5); F(); }
V>void D(){ print(4); E(); }
V>void C(){ print(3); D(); }
V>void B(){ print(2); C(); }
V>void A(){ print(1); B(); }

V>{ 
V>    A();  //точка входа
V>}
V>

V>то мы также получим сообщение что "stack depth exceeded", хотя никакой рекурсии, очевидно, и нет.
V>значит подходом с статик переменной мою задачу не решить и надо заводить доп. член на кажд ф-цию для хранения числа её вызовов. при вызове ф-ции мы инкрементируем этот счетчик, при выходе из нее -- декрементируем. если привышаем, скажем, 20, кидаем исключение как в коде выше. сейчас попробую. спасибо за помощь выше.

вы чета путаете. рекурсия не является проблемой, пока она не приводит к проблеме невычислимости. бесконечная рекурсия — это просто невычислимость. на попытку вычислить которую тратятся ресурсы и в конце концов истощаются.
что вас таким образом волнует?
счетчик на каждую функцию не является показательным. потому что рекурсия может быть косвенной, когда как в вашем этом примере N-функций будут друг друга вызывать по цепочке, и глубина стека(что есть на самом деле — глубина "вычислений") будет расти и потом последняя функция вызовет первую.
тогда при оьщей глубине стека в 2N вызовов, каждая функция будет вызвана только дважды.
вам на самом деле нужна именно глубина "вычислений", которая является показателем "сложности", и вам нужно ограничивать именно сложность.
то есть вам нужна именно общая переменная на все вызовы.
с учетом того, что если есть треды, нужно либо держать по такой переменной на каждый тред, либо иметь общую на все треды, но тогда делать доступ к ней атомарным или через мьютекс.

Здравствуйте, merk, Вы писали:
M>вам на самом деле нужна именно глубина "вычислений", которая является показателем "сложности", и вам нужно ограничивать именно сложность.
M>то есть вам нужна именно общая переменная на все вызовы.
теперь понял, угу. согласен. сразу как-то не мог все это в голове удержать.
M>с учетом того, что если есть треды, нужно либо держать по такой переменной на каждый тред, либо иметь общую на все треды, но тогда делать доступ к ней атомарным или через мьютекс.
тредов нету.
большое спасибо вам еще раз.

Добрый вечер, remark, Вы писали:

R>нельзя формально отделить бесконечную рекурсию от просто глубокой рекурсии (предложи критерий).
Вроде тут даже критерии не особо нужны — это утверждение математически доказывается (т.н. "проблема остановки")

R>з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.
Да! Я люблю Microsoft

Здравствуйте, Константин, Вы писали:

R>>нельзя формально отделить бесконечную рекурсию от просто глубокой рекурсии (предложи критерий).

К>Вроде тут даже критерии не особо нужны — это утверждение математически доказывается (т.н. "проблема остановки")

Можно переформулировать — как отличить очень глубокую желательную рекурсию от очень глубокой желательной рекурсии (ошибки в программе). Допустим глубина рекурсии зависит от входных данных, и формально останавливается. Домен входных данных компилятору не известен.

	От:	merk
	Дата:	09.07.08 18:13
	Оценка:

	От:	varnie
	Дата:	09.07.08 18:44
	Оценка:

	От:	merk
	Дата:	09.07.08 19:02
	Оценка:	3 (1)

	От:	merk
	Дата:	09.07.08 19:10
	Оценка:

	От:	varnie
	Дата:	09.07.08 19:42
	Оценка:

	От:	Константин
	Дата:	09.07.08 23:29
	Оценка:

От:	remark	http://www.1024cores.net/
Дата:	10.07.08 09:48
Оценка: