Бесконечная рекурсия без переполнения стека

Как-то я спорил с преподавателем. О чём, уже не помню , но помню, что мне для доказательства своей точки зрения надо было быть уверенным, что сабж невозможен. Собственно, в этом и вопрос: можно ли написать рекурсивную процедуру так, что она никогда (при определённом параметре, например) не вернёт управление, но и стек никогда не переполнится? Т.е. esp должен всё время колебаться в определённом интервале и никогда не выходить за его пределы. Можно делать что угодно: писать десять процедур, которые как-то друг друга вызывают, передавать вызов себя себе в качестве параметра и т.п., но соблюдать всегда два условия:
1) Прыжок назад запрещён.
2) Прямая модификация esp запрещена. Т.е. esp можно модифицировать только вызовом и возвратом из процедуры, а также в качестве выделения памяти для параметров и локальных переменных.
В том числе вот это тоже считается прямой модификацией esp:

Код (Text):

1. call recursion
2. recursion:
3.    pop eax
4.    call recursion
5. ret

 

l_inc, эээ, каждый call изменяет стек. Такова модель. Если еизменение убрать, то это не рекурсия а jumps.

 

l_inc
если размер кадра стека подпрограммы кратен степени двойки, если на машине не происходит прерываний при переходе sp с 0 к ~0, то указатель стека будет перемещаться по кольцу
так как рекурсия бесконечна, то невадно что данные будут затираться

 

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

 

.::del::.

 

рекурсия это
foo() {
if c1 then foo()
if c2 then foo()
...
}

тогда колебания уровней вложенности от 3 до 5
foo (n) {
do {
if (n<5) foo(n+1);
} while(n>3);
}

 

мм... прыжок назад запрещен... тогда это нерешаемо

 

Естественно. Это "недорекурсия", так сказать, ибо рекурсия всё ж предполагает возвраты.

 

эм....
Собственно вы сами огласили решения.
Прыжок назад и прямая модификация регистра esp

Ваша задача эквивалентна уравнению: 2h + 2h = x
найти х

Обязательные условия:
1. x не равен 4h
2. В каждом байте 32 бита.

 

Учитель не предполагала про существование селекторов, по причине того, что по дефолту в винде базы сегментов кода и данных нулевые )
В условии не сказано что их нельзя изменять.

 

s0larian
Я ж потому и написал, что вызов процедуры (call) допускается, как косвенная модификация esp. Не допускается прямая модификация esp (add esp,4, например, или пример из первого поста).
GoldFinch

Верно. Но это скорее аппартная реализация. В данном случае речь идёт об идее. Поэтому перезаписывание старых значений считается переполнением стека.
SII

Я разве написал, что возвращаться из процедуры вообще нельзя? Можно. Нельзя только из самого внешнего вызова.

Посмотрим на один из простейших примеров:

Код (Text):

1. lea ebx,[esp-18h]
2. lea esi,[esp-4]
3. xor eax,eax
4. call func
5. ret
6.  
7. func:
8.    cmp esp,ebx
9.    jbe @F
10.       call func
11.    @@:
12.    not eax
13.    test eax,eax
14.    jnz callAgain
15.    cmp esp,esi
16.    jb @F
17.       callAgain:
18.       call func
19.    @@:
20. ret

Для Вас с первого взгяда очевидно, терминирует функция или нет? Попробуйте её в потрассировать. ESP будет меняться только в одну сторону?
GoldFinch

do {} while - это вроде как прыжок назад. Т.е. для высокоуровневых языков запрещены goto, а также запрещены циклы. Остальное всё можно.
_int2e_

Может быть. Нужна только какая-нибудь инварианта, которая ясно покажет, что задача нерешаема.
Clerk
Любимая тема. Да нет... никаких аппаратно- или системно-зависимых решений.

Для высокоуровневых языков ещё раз слегка переформулирую задачу:
Запрещено использовать циклы (for, while, do и т.п.) и goto. Всё остальное допускается. Нужно доказать/опровергнуть, что с помощью рекурсии нельзя организовать бесконечный цикл. Переполнение стека означает обрыв цикла.

 

l_inc
В таком случае как может быть x - 4 > x, (x > 0)
А если подумать, то решение есть. Что делает процессор когда возникает исключение - он в Ss:Esp загружает значение определённое в TSS, поэтому можно бесконечно долго крутиться в рекурсии в режиме ядра. Например под стек отведена одна страница, которая адресуется Ss:Esp. Значит сохраняем мы это в сегменте состояния задачи и вызываем в цикле Call на саму себя. После 1k итераций возникнет исключение, Ss:Esp восстановятся в исходные значения, далее мы опять цикл вызываем.

 

Конечно не совсем корректное завершение, но на скорую руку думаю покатит.

Код (Text):

1. #include <windows.h>
2. #include <process.h>
3. #include <stdio.h>
4. #include <iostream>
5.  
6. unsigned int counter2 = 0;
7. unsigned int counter = 0;
8. CRITICAL_SECTION g_cs;
9. bool bstop = false;
10.  
11. unsigned __stdcall foo (void *counter1)
12. {
13.     EnterCriticalSection(&g_cs);
14.     counter = (unsigned int)counter1;
15.     if (0==counter1)
16.         counter2++;
17.     if (!bstop)
18.         _beginthreadex(0, 0, foo, (void*)(((unsigned int)counter1)+1), 0, 0);
19.     LeaveCriticalSection(&g_cs);
20.     return 0;
21. }
22.  
23.  
24. int main (int argc, char* argv[])
25. {
26.     InitializeCriticalSection(&g_cs);
27.     foo((void*)1);
28.     getchar();
29.     bstop = true;
30.     std::cout<<counter<<std::endl;
31.     std::cout<<counter2<<std::endl;
32.     Sleep(2000);
33. }

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

 

Clerk

Сравнение, если честно, не догнал.

Это аппаратно зависимое решение. Поэтому не подходит.
Booster
Создание потока с указанием себя стартовой точкой потока - это не рекурсия. К тому же системно зависимо.

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

 

l_inc
Что-то вроде такого.

Код (Text):

1. .386P
2. .MODEL FLAT, STDCALL
3.   EXTERN ExitProcess@4:NEAR
4.   INCLUDELIB d:\masm32\lib\kernel32.lib
5. ;-----------------------------------------------
6. _DATA SEGMENT DWORD PUBLIC USE32 'DATA'
7. _DATA ENDS
8. ;-----------------------------------------------
9. _TEXT SEGMENT DWORD PUBLIC USE32 'CODE'
10. START:
11.     MOV EBX, 0
12.     CALL FOO
13.     PUSH 1
14.     CALL ExitProcess@4
15. FOO PROC
16.     CMP EBX, 0
17.     MOV EBX, 1
18.     JNE _NO_CALL
19.     CALL FOO
20.     JMP _EXIT
21. _NO_CALL:
22.     MOV EBX, 0
23. _EXIT:
24.     MOV DWORD PTR [ESP], OFFSET FOO
25.     RET
26. FOO ENDP
27. _TEXT ENDS
28. END START

 

Booster
Ничего так понаписали. Я понимаю, что на... утро глядя, но зачем там ExitProcess? Да и с not всё таки лучше:

Код (Text):

1. CMP EBX, 0
2.     MOV EBX, 1
3.     JNE _NO_CALL
4.     CALL FOO
5.     JMP _EXIT
6. _NO_CALL:
7.     MOV EBX, 0
8. _EXIT:

практически равносильно

Код (Text):

1.    not ebx
2.    test ebx,ebx
3.    jz @F
4.       call foo
5.    @@:

Ладно. С учётом поставленных условий это верный вариант. На самом деле, конечно, адрес возврата менять нельзя.
Если быть абсолютно точным, то задача состоит в том, чтобы реализовать бесконечный цикл на языке OPAL. Циклы и прыжки там соответственно отсутствуют. Учитывая, что об этом языке здесь вряд ли кто-то слышал, я попытался сформулировать условия. Про запрет модификации адреса возврата забыл.

 

В функциональных языках отсутствуют (в pure-версиях) циклы и переменные. Существуют только функции и их параметры. Поэтому циклы реализуются через рекурсию:

Код (Text):

1. void func( int i )
2. {
3.   if ( i > 100 ) return;
4.   print( i );
5.   func( i + 1 );
6. };
7.  
8. func( 1 ); // распечатывает числа от 1 до 100 без циклов.

Все циклы в таких языках выполнены таким вот образом, поэтому встаёт существенный вопрос - что делать со стеком, если цикл будет до 4 миллиардов? На x86 это обязано привести к переполнению.
На самом деле интерпретаторы и компиляторы ФЯ анализируя ход работы в таких моментах по ряду признаков понимают что имеют дело не с полноценной рекурсией, а с цикловым воркэраундом и не продвигают стек, выполняя, по сути, JMP вместо CALL. Правила, кстати, несложные - что-то из серии того, что возвращаемое функцией значение нигде не используется и то что вызов рекурсии идет последним оператором в ней. Как-то так.
Видимо OPAL из этой серии.

 

Вчера не смог ответить. А что, если в зависимости от переданных параметров и полученного ответа от вызываемых функций, рекурсирующая функция будет делать retn x, где х - меняющаяся величина? Имхо это единственный способ влиять на стек в сторону увеличения esp при таких условиях. Если и это нельзя, то задача невозможна

 

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

 

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