1 | |
Как создать стек для рекурсивной функции?02.08.2015, 13:27. Показов 1670. Ответов 22
Метки нет (Все метки)
Здесь речь идёт вот о чем. Требуется сделать стек,
размер которого будет на порядок больше того, что может дать VB6. И основная проблема даже не в том как управлять этим стеком, а в том, что в него заносить, какие данные? Буду вам очень благодарен если вы приведёте маленький пример. Например надо вычислить 7!. И прокомментировать код. Все остальное я сделаю сам. Мне важно понять принцип. Принцип вызова рекурсивной функции и сохранение в стеке необходимых данных. Добавлено через 4 минуты В качестве стека я собираюсь использовать файл прямого (произвольного) доступа нужного мне размера.
0
|
02.08.2015, 13:27 | |
Ответы с готовыми решениями:
22
Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода и вывода элементов стека. Ввести эталонный символ. Создать отдельный стек для функции Применить стек для преобразования рекурсивной подпрограммы обхода дерева поиска в прямом порядке |
02.08.2015, 14:44 | 2 |
Был похожий вопрос в соседнем разделе.
Правда, VB6 с асмом не очень дружит и придется использовать опкоды. Нужна память, а не файл.
1
|
15153 / 6426 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
|
||||||
02.08.2015, 16:03 | 3 | |||||
Используйте старый бейсиковский механизм GoSub-Return. Простой тест показывает, что у этого механизма стек более чем на порядок больше!
1
|
Модератор
|
|
02.08.2015, 17:15 | 5 |
Это не рекурсия, это обычный цикл - локальные переменные для всех вызовов одинаковые, тоже можно сделать просто засунув тело в цикл While, тогда число вызовов вообще будет неограничено.
Размер стека настраивается в заголовке IMAGE_OPTIONAL_HEADER исполняемого файла. Кстати размер стека можно задать перед компиляцией - ключ /STACK компоновщика.
1
|
02.08.2015, 17:45 [ТС] | 6 |
The Trick, Вы бог программирования.
Не могли бы Вы спуститься на нашу грешную Землю и подсказать мне (доставить радость в Создании самого большого стека в мире), как сделать файловый стек. Только принцип. Ведь Адрес процедуры вещь постоянная. Её надо лишь раз запомнить. А локальные переменные? Ну допустим есть пара локальных переменных. У них тоже адреса постоянные? Или нет? Или да? Что идёт в стек? Их значения? Как? Последовательно при каждом обращении? Чувствую. Я где-то рядом с решением. Вы можете подсказать? Если не вы... Другим не решить. Они так глубоко не копают!
0
|
Модератор
|
|
02.08.2015, 17:58 | 7 |
Сообщение было отмечено echs как решение
Решение
Можно создать просто эмуляцию рекурсии в том числе через файл. На самом деле это будет уже нерекурсивная процедура.
Нет. В стек идут значения и адрес возврата + некоторые другие значения (зависит от ситуации). Значения кладутся в стек справа налево, т.е. если процедура имеет 5 параметров то значения кладутся начиная с 5-го, в конце кладется адрес возврата при каждом вызове (это для VB6).
1
|
02.08.2015, 18:02 | 8 |
Что подразумевается по этим? Такое впечатление что вместо памяти предлагается использовать файл...
Допустим функция вызывается рекурсивно и у нее есть локальные переменные. Будет ли затираться значение в переменных из предыдущего рекурсивного вызова функции? Ответ на этот вопрос позволит получить ответ на заданный вопрос. Можно посмотреть работу программы в отладчике. Если VB не поддерживает просмотр стека во время отладки программы, ее следует скомпилировать и запустить в чем-то типа ольки (OllyDbg).
1
|
02.08.2015, 18:21 [ТС] | 9 |
The Trick, большое спасибо.
Красиво! Вы вошли в мою звездную жизнь. Красиво уйдете, растаяв в лазури. Но стек я конечно создам... Как эскимо в шоколадной глазури! Большое Спасибо! Добавлено через 7 минут locm, Вы правы. Я хочу вместо оперативной памяти использовать файл. Ведь его размер может быть колоссальным. А доступ, при прямом доступе, достаточно быстрым. Впрочем скорость большого значения не имеет.
0
|
02.08.2015, 18:37 | 10 |
Процессор устроен так что может использовать стек только в оперативной памяти.
Разве что использовать SSD... Но как писал выше, железо компа не поддерживает создание стека в файле.
0
|
02.08.2015, 18:57 [ТС] | 11 |
locm,
Позвольте мне Вам возразить. Во-первых вы правы в том, что процессор не поддерживает файловый стек. Здесь я с вами согласен на все 100%. Но кто мешает нам создать файл прямого доступа, в котором будут определены операции записи в файл и считывания с него так, как это делается в стеке. Специальная переменная будет следить за наполняемостью файла-стека. И когда она станет равной нулю, то это будет означать, что стек чист и вычисление рекурсивной функции окончено. Вероятно это называется эмуляцией стека. Но дело не в терминах. Как бы это не называлось, я достаточно чётко ещё в самом начале темы об этом сказал. P.S. Возможно файл-стек и не будет чист, но нам это безразлично, ибо новая запись пойдёт поверх старой. Что левее указателя, то не существует.
0
|
03.08.2015, 06:36 [ТС] | 13 |
locm, спасибо!
Но я, кажется, нашёл способ сделать глубину рекурсии почти безграничной. В прошлом году я начал создавать программу Десятичный Ассемблер (DAS). Она сильно изменилась по сравнению с той, что я оставил на форуме. Именно там и будет неограниченный стек. Спасибо.
0
|
03.08.2015, 15:31 | 14 |
А у меня, если можно, смежный вопрос: как узнать какой объем стека заняла моя рекурсия в пике и сколько свободного осталось? Хочу узнать вероятность переполнения и может, при необходимости, пропатчить EXE.
0
|
03.08.2015, 16:09 | 15 | |||||
Как вариант, получить адрес указателя стека до рекурсии и в ее пике. Для этого нужно скопировать в переменную значение из регистра процессора esp (для x86 программы).
Как это будет выглядеть на VB точно не скажу, но дам пример на другом ЯП. Возможно будет понятно о чем я пишу.
1
|
Dragokas
|
03.08.2015, 16:32
#16
|
Не по теме: К сожалению, с ассемблером у меня плохо. Но спасибо, теперь хоть знаю направление.
0
|
03.08.2015, 19:56 | 18 | |||||
Так верно?
0
|
Модератор
|
||||||
03.08.2015, 22:02 | 19 | |||||
Вроде да.
Можешь проверить макс так:
1МБ. Добавлено через 3 минуты Зачем патчить? Есть же ключ компоновщика.
1
|
03.08.2015, 22:30 | 20 |
Код
/STACK:reserve[,commit]
Сообщение от MSDN
0
|
03.08.2015, 22:30 | |
03.08.2015, 22:30 | |
Помогаю со студенческими работами здесь
20
Разработать программу согласно алгоритму с использованием рекурсивной функции и без использования рекурсивной Как создать стек для ввода данных Как можно создать стек, с которым могли бы работать разные функции, записывать в него, удалять? Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |