Форум программистов, компьютерный форум, киберфорум
Visual Basic
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
1

Как создать стек для рекурсивной функции?

02.08.2015, 13:27. Показов 1670. Ответов 22
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здесь речь идёт вот о чем. Требуется сделать стек,
размер которого будет на порядок больше того, что
может дать VB6. И основная проблема даже не в том
как управлять этим стеком, а в том, что в него
заносить, какие данные? Буду вам очень благодарен
если вы приведёте маленький пример. Например
надо вычислить 7!. И прокомментировать код.
Все остальное я сделаю сам. Мне важно понять
принцип. Принцип вызова рекурсивной функции и
сохранение в стеке необходимых данных.

Добавлено через 4 минуты
В качестве стека я собираюсь использовать
файл прямого (произвольного) доступа
нужного мне размера.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.08.2015, 13:27
Ответы с готовыми решениями:

при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
Сабж g++ 4.5.0

Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода и вывода элементов стека. Ввести эталонный символ.
Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода...

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

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

22
Эксперт по электронике
5931 / 2647 / 282
Регистрация: 28.10.2011
Сообщений: 9,990
Записей в блоге: 6
02.08.2015, 14:44 2
Цитата Сообщение от geh Посмотреть сообщение
Требуется сделать стек, размер которого будет на порядок больше того, что может дать VB6.
Был похожий вопрос в соседнем разделе.
А вот нашёл, ну как и думал берёт память у системы и ставит свой esp.
В общем, нужно запросить у системы память и записать указатель на нее в регистр esp.
Правда, VB6 с асмом не очень дружит и придется использовать опкоды.

Цитата Сообщение от geh Посмотреть сообщение
В качестве стека я собираюсь использовать файл
Нужна память, а не файл.
1
15153 / 6426 / 1731
Регистрация: 24.09.2011
Сообщений: 9,999
02.08.2015, 16:03 3
Цитата Сообщение от geh Посмотреть сообщение
Требуется сделать стек, размер которого будет на порядок больше того, что может дать VB6.
Используйте старый бейсиковский механизм GoSub-Return. Простой тест показывает, что у этого механизма стек более чем на порядок больше!
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
Dim i&
 
Sub test()
  i = i + 1
  Debug.Print i 'Out of stack space при i=6801
  test
End Sub
 
Sub test1()
1 i = i + 1
  Debug.Print i 'Out of stack space при i=244809, в 36 раз больше!
  GoSub 1
End Sub
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
02.08.2015, 16:50  [ТС] 4
Ребята, большое спасибо!
Вы мне здорово помогли!
Теперь я сам разберусь с файловым стеком.
Ведь мне нужен именно он (!!)
Большое спасибо!
0
Модератор
9902 / 3806 / 879
Регистрация: 22.02.2013
Сообщений: 5,678
Записей в блоге: 78
02.08.2015, 17:15 5
Цитата Сообщение от Казанский Посмотреть сообщение
Используйте старый бейсиковский механизм GoSub-Return. Простой тест показывает, что у этого механизма стек более чем на порядок больше!
Это не рекурсия, это обычный цикл - локальные переменные для всех вызовов одинаковые, тоже можно сделать просто засунув тело в цикл While, тогда число вызовов вообще будет неограничено.
Размер стека настраивается в заголовке IMAGE_OPTIONAL_HEADER исполняемого файла.
Кстати размер стека можно задать перед компиляцией - ключ /STACK компоновщика.
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
02.08.2015, 17:45  [ТС] 6
The Trick, Вы бог программирования.
Не могли бы Вы спуститься на нашу грешную
Землю и подсказать мне (доставить радость в
Создании самого большого стека в мире), как
сделать файловый стек. Только принцип. Ведь
Адрес процедуры вещь постоянная. Её надо
лишь раз запомнить. А локальные переменные?
Ну допустим есть пара локальных переменных.
У них тоже адреса постоянные? Или нет? Или да?
Что идёт в стек? Их значения? Как? Последовательно
при каждом обращении? Чувствую. Я где-то рядом
с решением. Вы можете подсказать? Если не вы...
Другим не решить. Они так глубоко не копают!
0
Модератор
9902 / 3806 / 879
Регистрация: 22.02.2013
Сообщений: 5,678
Записей в блоге: 78
02.08.2015, 17:58 7
Лучший ответ Сообщение было отмечено echs как решение

Решение

Можно создать просто эмуляцию рекурсии в том числе через файл. На самом деле это будет уже нерекурсивная процедура.
Цитата Сообщение от geh Посмотреть сообщение
У них тоже адреса постоянные?
Нет.
Цитата Сообщение от geh Посмотреть сообщение
Что идёт в стек? Их значения? Как?
В стек идут значения и адрес возврата + некоторые другие значения (зависит от ситуации).
Цитата Сообщение от geh Посмотреть сообщение
Как? Последовательно
при каждом обращении?
Значения кладутся в стек справа налево, т.е. если процедура имеет 5 параметров то значения кладутся начиная с 5-го, в конце кладется адрес возврата при каждом вызове (это для VB6).
1
Эксперт по электронике
5931 / 2647 / 282
Регистрация: 28.10.2011
Сообщений: 9,990
Записей в блоге: 6
02.08.2015, 18:02 8
Цитата Сообщение от geh Посмотреть сообщение
как сделать файловый стек
Что подразумевается по этим? Такое впечатление что вместо памяти предлагается использовать файл...

Цитата Сообщение от geh Посмотреть сообщение
А локальные переменные?
Ну допустим есть пара локальных переменных.
У них тоже адреса постоянные? Или нет? Или да?
Допустим функция вызывается рекурсивно и у нее есть локальные переменные. Будет ли затираться значение в переменных из предыдущего рекурсивного вызова функции? Ответ на этот вопрос позволит получить ответ на заданный вопрос.

Цитата Сообщение от geh Посмотреть сообщение
Что идёт в стек? Их значения? Как? Последовательно при каждом обращении?
Можно посмотреть работу программы в отладчике. Если VB не поддерживает просмотр стека во время отладки программы, ее следует скомпилировать и запустить в чем-то типа ольки (OllyDbg).
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
02.08.2015, 18:21  [ТС] 9
The Trick, большое спасибо.

Красиво! Вы вошли в мою звездную жизнь.
Красиво уйдете, растаяв в лазури.
Но стек я конечно создам...
Как эскимо в шоколадной глазури!

Большое Спасибо!

Добавлено через 7 минут
locm,
Вы правы. Я хочу вместо оперативной памяти
использовать файл. Ведь его размер может
быть колоссальным. А доступ, при прямом
доступе, достаточно быстрым. Впрочем
скорость большого значения не имеет.
0
Эксперт по электронике
5931 / 2647 / 282
Регистрация: 28.10.2011
Сообщений: 9,990
Записей в блоге: 6
02.08.2015, 18:37 10
Цитата Сообщение от geh Посмотреть сообщение
Я хочу вместо оперативной памяти использовать файл.
Процессор устроен так что может использовать стек только в оперативной памяти.

Цитата Сообщение от geh Посмотреть сообщение
А доступ, при прямом доступе, достаточно быстрым.
Разве что использовать SSD...
Но как писал выше, железо компа не поддерживает создание стека в файле.
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
02.08.2015, 18:57  [ТС] 11
locm,
Позвольте мне Вам возразить.
Во-первых вы правы в том, что процессор не
поддерживает файловый стек. Здесь я с вами
согласен на все 100%. Но кто мешает нам создать
файл прямого доступа, в котором будут определены
операции записи в файл и считывания с него так, как
это делается в стеке. Специальная переменная будет
следить за наполняемостью файла-стека. И когда она
станет равной нулю, то это будет означать, что стек
чист и вычисление рекурсивной функции окончено.
Вероятно это называется эмуляцией стека. Но дело
не в терминах. Как бы это не называлось, я достаточно
чётко ещё в самом начале темы об этом сказал.
P.S.
Возможно файл-стек и не будет чист, но
нам это безразлично, ибо новая запись
пойдёт поверх старой. Что левее указателя,
то не существует.
0
Эксперт по электронике
5931 / 2647 / 282
Регистрация: 28.10.2011
Сообщений: 9,990
Записей в блоге: 6
02.08.2015, 19:35 12
Это должно работать. Но вложенность вызовов функции от этого не увеличится, т. к. адрес возврата и локальные переменные по прежнему будут в памяти.
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
03.08.2015, 06:36  [ТС] 13
locm, спасибо!
Но я, кажется, нашёл способ сделать
глубину рекурсии почти безграничной.
В прошлом году я начал создавать программу
Десятичный Ассемблер (DAS). Она сильно
изменилась по сравнению с той, что я оставил
на форуме. Именно там и будет неограниченный стек.
Спасибо.
0
Эксперт WindowsАвтор FAQ
17984 / 7713 / 892
Регистрация: 25.12.2011
Сообщений: 11,492
Записей в блоге: 16
03.08.2015, 15:31 14
А у меня, если можно, смежный вопрос: как узнать какой объем стека заняла моя рекурсия в пике и сколько свободного осталось? Хочу узнать вероятность переполнения и может, при необходимости, пропатчить EXE.
0
Эксперт по электронике
5931 / 2647 / 282
Регистрация: 28.10.2011
Сообщений: 9,990
Записей в блоге: 6
03.08.2015, 16:09 15
Цитата Сообщение от Dragokas Посмотреть сообщение
как узнать какой объем стека заняла моя рекурсия в пике
Как вариант, получить адрес указателя стека до рекурсии и в ее пике. Для этого нужно скопировать в переменную значение из регистра процессора esp (для x86 программы).
Как это будет выглядеть на VB точно не скажу, но дам пример на другом ЯП. Возможно будет понятно о чем я пишу.
PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Global StackAddr
 
EnableASM
 
Macro GetStackAddr(Var)
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
    MOV Var, esp  ; x86.
  CompilerElse
    MOV Var, rsp  ; x64.
  CompilerEndIf
EndMacro
 
Procedure Tst(i)
  If i<10      ; Прервать рекурсию если ее глубина равна 10.
    Tst(i+1)
  ElseIf i=10
    GetStackAddr(i) ; Копирование текущего адреса стека в переменную.
    MessageRequester("", "Было использовано "+Str(StackAddr-i)+" байт стека")
  EndIf
EndProcedure
 
 
GetStackAddr(StackAddr) ; Копирование текущего адреса стека в переменную.
Tst(0)
1
Dragokas
03.08.2015, 16:32
  #16

Не по теме:

К сожалению, с ассемблером у меня плохо. Но спасибо, теперь хоть знаю направление.

0
Модератор
9902 / 3806 / 879
Регистрация: 22.02.2013
Сообщений: 5,678
Записей в блоге: 78
03.08.2015, 17:19 17
Получить адрес переменной в стеке при первом вызове и при последнем и найти разницу
1
Эксперт WindowsАвтор FAQ
17984 / 7713 / 892
Регистрация: 25.12.2011
Сообщений: 11,492
Записей в блоге: 16
03.08.2015, 19:56 18
Так верно?

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Option Explicit
 
Dim AddrStart As Long
Dim AddrEnd As Long
 
Private Sub Form_Load()
  Tst 0
  Debug.Print "Было использовано " & (AddrEnd - AddrStart) & " байт стека"
End Sub
 
Sub Tst(ByVal i As Long)
  If AddrEnd = 0 Then AddrEnd = VarPtr(i)
  If i < 10 Then
    i = (i + 1)
    Tst i
  Else
    AddrStart = VarPtr(i)
  End If
End Sub
А какой дефолтный размер стека?
0
Модератор
9902 / 3806 / 879
Регистрация: 22.02.2013
Сообщений: 5,678
Записей в блоге: 78
03.08.2015, 22:02 19
Цитата Сообщение от Dragokas Посмотреть сообщение
Так верно?
Вроде да.
Можешь проверить макс так:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Dim first   As Long
Dim last    As Long
 
Private Sub Form_Load()
    On Error GoTo getStack
    foo 0
    
getStack:
    
    MsgBox Hex(first - last)
    
End Sub
 
Private Sub foo(ByVal z As Long)
 
    If z = 0 Then
        first = VarPtr(z)
        z = 1
    Else
        last = VarPtr(z)
    End If
 
    foo z
    
End Sub
Ну тут стоит учесть что вызов метода занимает больше памяти.
Цитата Сообщение от Dragokas Посмотреть сообщение
А какой дефолтный размер стека?
1МБ.

Добавлено через 3 минуты
Цитата Сообщение от Dragokas Посмотреть сообщение
пропатчить EXE.
Зачем патчить? Есть же ключ компоновщика.
1
Эксперт WindowsАвтор FAQ
17984 / 7713 / 892
Регистрация: 25.12.2011
Сообщений: 11,492
Записей в блоге: 16
03.08.2015, 22:30 20
Код
/STACK:reserve[,commit]
Цитата Сообщение от MSDN
Значение параметра commit интерпретируется операционной системой. В Windows WindowsRT он определяет объем физической памяти для выделения одновременно. Выделенная виртуальная память резервирует пространство в файле разбиения по страницам. Более высокое commit значение позволяет сэкономить время, когда приложению требуется большее пространство стека, но увеличивает требования к памяти и по возможности времени запуска. Для ARM x86 и компьютеры x64, фиксация значение по умолчанию 4 КБ.
Весьма сносно понял смысл commit. Это объем, выделяемый на физическом диске, когда заканчивается стек?
0
03.08.2015, 22:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.08.2015, 22:30
Помогаю со студенческими работами здесь

Разработать программу согласно алгоритму с использованием рекурсивной функции и без использования рекурсивной
Разработать программу согласно алгоритму с использованием рекурсивной функции и без использования...

Как создать стек для ввода данных
Данные ниже правильно написаны для добавления в стринггрид? p^.fio:=edi1.text; stringgrid1.cells;...

Как можно создать стек, с которым могли бы работать разные функции, записывать в него, удалять?
Здравствуйте! Только начала знакомиться с функциональным программирование и Haskell. Возникли...

Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru