Рекурсивная функция и размер стека

Здравствуйте.
Возникла тут у меня проблема: Нужно реализовать рекурсивную функцию (вроде бы называется функцией Аккермана) : A(0,M)=M+1; A(N,0)=A(N-1,1); A(N,M)=A(N-1,A(N,M-1)). Я ее написал на NASM (линковал майкрософтовским link'ом), использовал соглашение stdcall. Вычисляется она вроде правильно, например A(3,12)=32765, вычислялось примерно 5 секунд. Но если я ввожу параметры (3,13) , то спустя несколько секунд программа просто прекращает свою работу (завершается), хотя после вычисления значения функции она должна вывести в консоль результат (регистр eax). Я подумал, что возможно происходит переполнение стека, но не нашел параметра в NASM'e устанавливающего размер стека. Быть может я неправильно понимаю суть проблемы.
Просьба к тем кто знает в чем причина такого поведения программы, или как устанавливать в NASM размер стека, ответить пожалуйста.
Вот собственно функция (кусок из главной программы):
akkerman:
push ebp
mov ebp,esp
push ebx
xor eax,eax
cmp dword [ebp+8],0
jne qq
mov eax,[ebp+12]
inc eax
jmp ex
qq:
cmp dword [ebp+12],0
jne ww
mov eax,[ebp+8]
dec eax
push dword 1
push eax
call akkerman
jmp ex
ww:
mov ebx,[ebp+12]
dec ebx
push ebx
mov ebx, [ebp+8]
push ebx
call akkerman
push eax
mov eax,[ebp+8]
dec eax
push eax
call akkerman
ex:
pop ebx
pop ebp
ret 8

P.S. Почему именно в NASM ? После того как у меня появилась эта проблема это стало уже делом принципа ).

 

ntp
На NASM никогда ничего не писал, поэтому отвечу со своей колокольни
1) Отладчик, чтобы убедиться в переполнении стэка. Хотя 99%, что проблема именно в нём.
2) Вообще не догнал, зачем использовать ebx. Чтобы была возможность быстрее засорить стэк, сохраняя его в начале и в конце функции?
3) Открываете скомпилированный экзешник и правите руками в HEX-редакторе поля SizeOfStackReserve и SizeOfStackCommit, сколько влезет.
4) Можете вообще свой собственный стэк сделать: просто выделяете памяти сколько нужно и запихиваете в esp адрес конца этой памяти.
5) Какой смысл вообще в том, чтобы стэк увеличивать? Ну сможете Вы A(3,13) высчитать... а, например, для A(3,150) Вам вообще никакой памяти не хватит.

P.S. И адресацию аргументов, кстати, через esp стоит сделать, а не через ebp. Если при этом и ebx не сохранять, то по идее A(3,13) можно ещё высчитать без увеличения размера стэка.

 

To l_inc:
1) Сейчас прогнал прогу под OllyDbg. Похоже действительно переполнение стека. В конце работы функции участок кода зацикливается, а ESP постоянно растет. Вообще конечно у меня мало опыта, поэтому к Вам просьба запустить мою программу: http://slil.ru/26244385 под отладчиком и посмотреть что же там все таки происходит.
2) Конечно ebx там вовсе не нужен, это я так сказать, затупил. Из программы убрал push ebx и pop ebx, а так же заменил везде где он использовался на eax. Проблема осталась.
3) Сейчас буду смотреть формат PE, чтобы, как Вы сказали, вручную править SizeOfStackReserve и SizeOfStackCommit. Если Вас не затруднит, скажите мне смещения в exe-файле для этих параметров и прокометируйте что они означают. Я вообще-то еще пробовал при линковке указывать параметр /STACK:xxx , но положительного результата это не дало.
4) Про свой стек из динамической памяти я уже думал, ну хотелось бы разобраться с этой батвой.
5) Стек увеличивать как раз чтобы посчитать A(3,13), здесь, как я уже говорил, дело принципа )

 

Угу, там действительно переполнение стека. Для параметров (3,13) общее число стековых фреймов 65535, размер каждого - 0x10 байт (два аргумента, адрес возврата и ebp), перемножая, получаем как раз мегабайт, а ровно столько по умолчанию и отводится под стек; с учётом нужд системы и вызывающей программы стека не хватает.

Тогда в командную строку линкера нужно добавить что-то типа /stack:0x200000 (для двух мегабайт) - будет работать.
P.S. Присоединяюсь к l_inc: при адресации аргументов через esp стека должно хватить.

 

ntp
Рекурсия - зло ) переделай её в цикл, тем более проблем абсолютно никаких и не парься
Имхо рекурсия оправдана в математике (аналитической, а не вычислительной) и в экзотических макросах (которые соответсвенно стек на засоряют . А в остальных случаях от её замены на цикл прога улучшается и по читаемости и исчезает бессмысленная ресуроёмкость.

 

/holywar
Y_Mur
а как же рекурсивный поиск в дереве, синтаксический анализ, и еще много алгоритмов где без рекурсии никак?

 

о пользе/вреде рекурсии была уже тема:
http://wasm.ru/forum/viewtopic.php?id=27488

 

Тут можно fastcall использовать и вообще исключить сохранение параметров в стэке, т.к. единственный сохраняемый параметр это N и изменяется он всегда одинаково на -1, поэтому его можно просто восстанавливать при выходе из процедуры

Код (Text):

1. ;A(0,M)=M+1
2. ;A(N,0)=A(N-1,1)
3. ;A(N,M)=A(N-1,A(N,M-1))
4. akkerman:
5. ;IN: ecx = N, edx = M
6. ;OUT eax = result, ecx = N
7.   test ecx,ecx
8.   jnz qq
9.   lea eax,[edx+1]
10.   retn
11. qq:
12.   test edx,edx
13.   jnz ww
14.   inc edx
15.   dec ecx
16.   call akkerman
17.   inc ecx ;восстанавливаем N при выходе
18.   retn
19. ww:
20.   dec edx
21.   call akkerman
22.   mov edx,eax
23.   dec ecx
24.   call akkerman
25.   inc ecx ;восстанавливаем N при выходе
26.   retn

В этом сл.в стэк пишутся только адреса возврата и памяти требуется в 4 раза меньше по ср. с первоначальным вариантом
PS: если нужен stdcall, то можно обернуть fastcall в "фантик"

 

GoldFinch
В дереве и т.п. ничего не мешает сотворить в памяти свой аналог стека и класть в него только те данные, которые нужно сохранить, а не пихать всё подряд
С точки зрения логики программы совсем ничего не меняется, а бессмысленная трата ресурсов исчезает

varnie
Тему видел, но она шибко философски-флудовая, потому даже и участвовать в той заварушке не стал
А здесь конкретный пример, где 3 переменные, которые даже в память класть не нужно, можно в регистрах разместить и которые используются, только при "прямом ходе" алгоритма, а при "раскрутке стека" ret-ами просто выкидываются и ради этого дикий расход стека? сопряжённый с торможением выделения страниц памяти, да и предсказатель ret тоже не резиновый, значит + тормоза от неверно предсказанных переходов.

Гы-Гы ))

 

To diamond:
Прописал как Вы сказали /stack:0x200000. Значение A(3,13) вычислилось - 65533. Хотелось бы узнать до скольки можно увеличивать этот параметр? Теперь функция загибается при (3,14).

Я мб кое чего не понимаю, но скажите, как Вы это посчитали ?

To Y_Mur:

Извините, но что значит переделай ее в цикл? Или здесь имеется ввиду свой стек из динамической памяти?

Сейчас такая реализация задачи принципиально неприемлима.

To leo:
Проверил предложенный Вами пример. Действительно, использовать регистры в контексте данной задачи, весьма удобно. Посчитал A(3,14)=131069. Теперь скажите пожалуйста как можно обернуть fastcall в "фантик" stdcall?

 

Какбэ это тоже есть рекурсия, а "аппаратный" стек или "программный" - это уже детали реализации.

 

GoldFinch
Дерево можно положить в массив, и обходить соответственно в цикле.
Y_Mur

Это тоже полумера, так как всё равно неизвестно сколько нужно памяти, хотя и решаема так как стек аппаратный фиксирован, а самопальный нет.

ntp
Увеличить стек, наверняка есть соответствующая опция компилятора. Ну а если критично, отказываться от рекурсии.

 

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

 

To Booster:

Сейчас эксперементирую с параметром линкера /stack. Хотелось бы знать на сколько можно поднимать размер стека.
Отказаться от рекурсии ? Извольте, но разве эту задачу можо решить не используя рекурсию ?

P.S. /stack 0x400000 вычисляется A(3,14)

 

GoldFinch

Замкнутый круг получается. Но я писал только то, что его можно положить в массив, а не о том как его строить.

 

Просто

Код (Text):

1. GetAkkerman: ;stdcall-фантик
2.   push ebp
3.   mov ebp,esp
4.   mov ecx,[ebp+8]
5.   mov edx,[ebp+12]
6.   call akkerman
7.   ;mov esp,ebp
8.   pop ebp
9.   retn 8
10. allign 4
11. akkerman: ;fastcall-пряник
12.   ...

Сколько душе угодно, но в пределах разумного

Наверняка можно, если не полностью, то хотя бы частично заменить на циклы. Например, при A(N,M)=A(N-1,A(N,M-1)) происходит вызов функции M раз только для того, чтобы сделать декремент M и "загадить" стек. Тоже самое с A(N,0)

 

ntp

Вижу, на данный момент необходимость отпала уже.

Хм...
DWORD[3Ch]+60h - смещение SizeOfStackReserve
DWORD[3Ch]+64h - смещение SizeOfStackCommit,
где [] - операция разыменования смещения.
SizeOfStackReserve - сколько памяти зарезервировать под стэк (при превышении размером стэка этой величины возникает переполнение)
SizeOfStackCommit - сколько памяти выделить под стэк

 

Если обозначить общее число стековых фреймов для параметров (n,m) через, скажем, f(n,m), то на f выписываются рекуррентные соотношения
f(0,m) = 1 (нет рекурсивных вызовов, только один главный)
f(n,0) = 1+f(n-1,1) (один главный вызов функции и вложенные в главный фреймы для вычисления A(n-1,1))
f(n,m) = 1+max(f(n,m-1),f(n-1,A(n,m-1))) (один главный вызов, вложеннные в главный фреймы для вычисления A(n,m-1) и независимо от них ещё фреймы для вычисления A(n-1,A(n,m-1))). А отсюда уже всё считается. Например, f(3,m) = 2^(m+3)-1.

Между прочим, для малых фиксированных значений n для функции Аккермана есть простые формулы:
A(0,m) = m+1
A(1,m) = m+2
A(2,m) = 2m+3
A(3,m) = 2^(m+3)-3
а при больших она просто слишком быстро растёт: уже N(4,2) = 2^65536-3, N(4,3) = 2^(2^65536)-3, что ни в какую память не влезет, так что вычислять значения невозможно.

 

leo

Код (Text):

1. ;A(0,M)=M+1
2. ;A(N,0)=A(N-1,1)
3. ;A(N,M)=A(N-1,A(N,M-1))
4. akkerman:
5. ;IN: ecx = N, edx = M
6. ;OUT eax = result, ecx = N
7.   test ecx,ecx
8.   jnz qq
9.   lea eax,[edx+1]
10.   retn
11. qq:
12.   test edx,edx
13.   jnz ww
14.   inc edx
15.   dec ecx
16.   call akkerman
17.   inc ecx ;восстанавливаем N при выходе
18.   retn
19. ww:
20.   dec edx
21.   call akkerman
22.   mov edx,eax
23.   dec ecx
24.   call akkerman
25.   inc ecx ;восстанавливаем N при выходе
26.   retn

Тут, кстати, можно приколоться с кустарным стеком: если внимательно посмотреть, то видно, что пихаемый в стек адрес возврата может принимать только 4 значения (от вызывающей функции и от трёх мест рекурсивного вызова). Так что можно создать стек, хранящий двубитовые значения, и интерпретировать его элементы как метки возврата. Тогда потребности в памяти уменьшатся в 16 раз, что даст возможность при тех же ограничениях вычислить значения A(3,m) с m аж на 4 большим