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

echs · Регистрация: 23.10.2013

Студворк — интернет-сервис помощи студентам

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

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

@locm · 02.08.2015, 14:44

Сообщение от geh

Требуется сделать стек, размер которого будет на порядок больше того, что может дать VB6.

Был похожий вопрос в соседнем разделе.

А вот нашёл, ну как и думал берёт память у системы и ставит свой esp.

В общем, нужно запросить у системы память и записать указатель на нее в регистр esp.
Правда, VB6 с асмом не очень дружит и придется использовать опкоды.

Сообщение от geh

В качестве стека я собираюсь использовать файл

Нужна память, а не файл.

@Казанский · 02.08.2015, 16:03

Сообщение от 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

echs · 02.08.2015, 16:50 **[ТС]**

Ребята, большое спасибо!
Вы мне здорово помогли!
Теперь я сам разберусь с файловым стеком.
Ведь мне нужен именно он (!!)
Большое спасибо!

@The trick · 02.08.2015, 17:15

Сообщение от Казанский

Используйте старый бейсиковский механизм GoSub-Return. Простой тест показывает, что у этого механизма стек более чем на порядок больше!

Это не рекурсия, это обычный цикл - локальные переменные для всех вызовов одинаковые, тоже можно сделать просто засунув тело в цикл While, тогда число вызовов вообще будет неограничено.
Размер стека настраивается в заголовке IMAGE_OPTIONAL_HEADER исполняемого файла.
Кстати размер стека можно задать перед компиляцией - ключ /STACK компоновщика.

echs · 02.08.2015, 17:45 **[ТС]**

The Trick, Вы бог программирования.
Не могли бы Вы спуститься на нашу грешную
Землю и подсказать мне (доставить радость в
Создании самого большого стека в мире), как
сделать файловый стек. Только принцип. Ведь
Адрес процедуры вещь постоянная. Её надо
лишь раз запомнить. А локальные переменные?
Ну допустим есть пара локальных переменных.
У них тоже адреса постоянные? Или нет? Или да?
Что идёт в стек? Их значения? Как? Последовательно
при каждом обращении? Чувствую. Я где-то рядом
с решением. Вы можете подсказать? Если не вы...
Другим не решить. Они так глубоко не копают!

@The trick · 02.08.2015, 17:58

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

Сообщение от geh

У них тоже адреса постоянные?

Нет.

Сообщение от geh

Что идёт в стек? Их значения? Как?

В стек идут значения и адрес возврата + некоторые другие значения (зависит от ситуации).

Сообщение от geh

Как? Последовательно
при каждом обращении?

Значения кладутся в стек справа налево, т.е. если процедура имеет 5 параметров то значения кладутся начиная с 5-го, в конце кладется адрес возврата при каждом вызове (это для VB6).

@locm · 02.08.2015, 18:02

Сообщение от geh

как сделать файловый стек

Что подразумевается по этим? Такое впечатление что вместо памяти предлагается использовать файл...

Сообщение от geh

А локальные переменные?
Ну допустим есть пара локальных переменных.
У них тоже адреса постоянные? Или нет? Или да?

Допустим функция вызывается рекурсивно и у нее есть локальные переменные. Будет ли затираться значение в переменных из предыдущего рекурсивного вызова функции? Ответ на этот вопрос позволит получить ответ на заданный вопрос.

Сообщение от geh

Что идёт в стек? Их значения? Как? Последовательно при каждом обращении?

Можно посмотреть работу программы в отладчике. Если VB не поддерживает просмотр стека во время отладки программы, ее следует скомпилировать и запустить в чем-то типа ольки (OllyDbg).

echs · 02.08.2015, 18:21 **[ТС]**

The Trick, большое спасибо.

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

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

Добавлено через 7 минут
locm,
Вы правы. Я хочу вместо оперативной памяти
использовать файл. Ведь его размер может
быть колоссальным. А доступ, при прямом
доступе, достаточно быстрым. Впрочем
скорость большого значения не имеет.

@locm · 02.08.2015, 18:37

Сообщение от geh

Я хочу вместо оперативной памяти использовать файл.

Процессор устроен так что может использовать стек только в оперативной памяти.

Сообщение от geh

А доступ, при прямом доступе, достаточно быстрым.

Разве что использовать SSD...
Но как писал выше, железо компа не поддерживает создание стека в файле.

echs · 02.08.2015, 18:57 **[ТС]**

locm,
Позвольте мне Вам возразить.
Во-первых вы правы в том, что процессор не
поддерживает файловый стек. Здесь я с вами
согласен на все 100%. Но кто мешает нам создать
файл прямого доступа, в котором будут определены
операции записи в файл и считывания с него так, как
это делается в стеке. Специальная переменная будет
следить за наполняемостью файла-стека. И когда она
станет равной нулю, то это будет означать, что стек
чист и вычисление рекурсивной функции окончено.
Вероятно это называется эмуляцией стека. Но дело
не в терминах. Как бы это не называлось, я достаточно
чётко ещё в самом начале темы об этом сказал.
P.S.
Возможно файл-стек и не будет чист, но
нам это безразлично, ибо новая запись
пойдёт поверх старой. Что левее указателя,
то не существует.

@locm · 02.08.2015, 19:35

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

echs · 03.08.2015, 06:36 **[ТС]**

locm, спасибо!
Но я, кажется, нашёл способ сделать
глубину рекурсии почти безграничной.
В прошлом году я начал создавать программу
Десятичный Ассемблер (DAS). Она сильно
изменилась по сравнению с той, что я оставил
на форуме. Именно там и будет неограниченный стек.
Спасибо.

Dragokas · 03.08.2015, 15:31

А у меня, если можно, смежный вопрос: как узнать какой объем стека заняла моя рекурсия в пике и сколько свободного осталось? Хочу узнать вероятность переполнения и может, при необходимости, пропатчить EXE.

@locm · 03.08.2015, 16:09

Сообщение от 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)

Dragokas · 03.08.2015, 16:32

Не по теме:

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

@The trick · 03.08.2015, 17:19

Получить адрес переменной в стеке при первом вызове и при последнем и найти разницу

Dragokas · 03.08.2015, 19:56

Так верно?

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

А какой дефолтный размер стека?

@The trick · 03.08.2015, 22:02

Сообщение от 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.

Зачем патчить? Есть же ключ компоновщика.

Dragokas · 03.08.2015, 22:30

Code
1
/STACK:reserve[,commit]

Сообщение от MSDN

Значение параметра commit интерпретируется операционной системой. В Windows WindowsRT он определяет объем физической памяти для выделения одновременно. Выделенная виртуальная память резервирует пространство в файле разбиения по страницам. Более высокое commit значение позволяет сэкономить время, когда приложению требуется большее пространство стека, но увеличивает требования к памяти и по возможности времени запуска. Для ARM x86 и компьютеры x64, фиксация значение по умолчанию 4 КБ.

Весьма сносно понял смысл commit. Это объем, выделяемый на физическом диске, когда заканчивается стек?

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8

	Как создать стек для рекурсивной функции? 02.08.2015, 13:27. Показов 1908. Ответов 22 Метки нет (Все метки) Здесь речь идёт вот о чем. Требуется сделать стек, размер которого будет на порядок больше того, что может дать VB6. И основная проблема даже не в том как управлять этим стеком, а в том, что в него заносить, какие данные? Буду вам очень благодарен если вы приведёте маленький пример. Например надо вычислить 7!. И прокомментировать код. Все остальное я сделаю сам. Мне важно понять принцип. Принцип вызова рекурсивной функции и сохранение в стеке необходимых данных. Добавлено через 4 минуты В качестве стека я собираюсь использовать файл прямого (произвольного) доступа нужного мне размера. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.08.2015, 16:50 [ТС]
	Ребята, большое спасибо! Вы мне здорово помогли! Теперь я сам разберусь с файловым стеком. Ведь мне нужен именно он (!!) Большое спасибо! 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.08.2015, 17:45 [ТС]
	The Trick, Вы бог программирования. Не могли бы Вы спуститься на нашу грешную Землю и подсказать мне (доставить радость в Создании самого большого стека в мире), как сделать файловый стек. Только принцип. Ведь Адрес процедуры вещь постоянная. Её надо лишь раз запомнить. А локальные переменные? Ну допустим есть пара локальных переменных. У них тоже адреса постоянные? Или нет? Или да? Что идёт в стек? Их значения? Как? Последовательно при каждом обращении? Чувствую. Я где-то рядом с решением. Вы можете подсказать? Если не вы... Другим не решить. Они так глубоко не копают! 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.08.2015, 18:21 [ТС]
	The Trick, большое спасибо. Красиво! Вы вошли в мою звездную жизнь. Красиво уйдете, растаяв в лазури. Но стек я конечно создам... Как эскимо в шоколадной глазури! Большое Спасибо! Добавлено через 7 минут locm, Вы правы. Я хочу вместо оперативной памяти использовать файл. Ведь его размер может быть колоссальным. А доступ, при прямом доступе, достаточно быстрым. Впрочем скорость большого значения не имеет. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.08.2015, 18:57 [ТС]
	locm, Позвольте мне Вам возразить. Во-первых вы правы в том, что процессор не поддерживает файловый стек. Здесь я с вами согласен на все 100%. Но кто мешает нам создать файл прямого доступа, в котором будут определены операции записи в файл и считывания с него так, как это делается в стеке. Специальная переменная будет следить за наполняемостью файла-стека. И когда она станет равной нулю, то это будет означать, что стек чист и вычисление рекурсивной функции окончено. Вероятно это называется эмуляцией стека. Но дело не в терминах. Как бы это не называлось, я достаточно чётко ещё в самом начале темы об этом сказал. P.S. Возможно файл-стек и не будет чист, но нам это безразлично, ибо новая запись пойдёт поверх старой. Что левее указателя, то не существует. 0

@locm 6850 / 3274 / 339 Регистрация: 28.10.2011 Сообщений: 12,796 Записей в блоге: 7
	02.08.2015, 19:35
	Это должно работать. Но вложенность вызовов функции от этого не увеличится, т. к. адрес возврата и локальные переменные по прежнему будут в памяти. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	03.08.2015, 06:36 [ТС]
	locm, спасибо! Но я, кажется, нашёл способ сделать глубину рекурсии почти безграничной. В прошлом году я начал создавать программу Десятичный Ассемблер (DAS). Она сильно изменилась по сравнению с той, что я оставил на форуме. Именно там и будет неограниченный стек. Спасибо. 0

Dragokas 18033 / 7736 / 892 Регистрация: 25.12.2011 Сообщений: 11,502 Записей в блоге: 16
	03.08.2015, 15:31
	А у меня, если можно, смежный вопрос: как узнать какой объем стека заняла моя рекурсия в пике и сколько свободного осталось? Хочу узнать вероятность переполнения и может, при необходимости, пропатчить EXE. 0

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

@The trick Модератор 10057 / 3902 / 884 Регистрация: 22.02.2013 Сообщений: 5,853 Записей в блоге: 79
	03.08.2015, 17:19
	Получить адрес переменной в стеке при первом вызове и при последнем и найти разницу 1

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

Решение