Теория: рекурсивная функция и регистр указателя стека

То, что переполнится регистр - это не так страшно, т.к. быстрее кончится память, на которую он указывает. А еще обычно в стек на каждом вызове кладется всякое добро типа адреса возврата и локальных переменных, так что регистр будет увеличиваться намного быстрее, чем на единицу за вызов. Для общего развития можно посмотреть на тему «хвостовая рекурсия»

Если функция с хвостовой рекурсией, то можешь хоть увызываться, SP меняться не будет.

в регистре SP просто указатель на вершину стека

Угу.

при вызове функции, указатель на вершину стека растёт на 4

Если ничего через стек не передается. Туда заталкивается адрес возврата.

похоже пора на ЛОРе создавать раздел «букварь». Или «нубятня». Как-то так...

2^32 / 4 = 1073741824, как 16 тыщ-то получилось?

как уже выше сказали, не 16к, а немножко больше. Но главное даже не это, главное, если будет такая рекурсия, то не пора ли руки оптимизировать до локтя? Даже для теории))

не лучше ли написать функции push и pop для данных

Для начала все рекурсии можно переделать в итерацию (даже нехвостовые).

Есть ли возможность на языке C обойти это ограничение, или в данном случае оно серьёзно завязано на конкретный процессор?

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

Если заменить реальные регистры «виртуальными», можно здорово увеличить ресурсы.

В твоём неконкретном примере можно заменить SP счётчиком вызовов в памяти: теряется деление на 4, счетчик можно сделать 64/128/100500 битным. Соответственно функция циклится в «прямом» направлении, а потом в обратном (можно разбить на две, чтоб условие не вводить).

Язык естественно не имеет значения.

Если функция с хвостовой рекурсией, то можешь хоть увызываться, SP меняться не будет.

Лютое 4.2

Не путайте хвостовую рекурсию и оптимизацию хвостовой рекурсии.

ок, уел. Да, я не прав.

все рекурсии можно переделать в итерацию (даже нехвостовые).

Говорят, ф-я Аккерамана опровергает это утверждение.

«Врут, врут, собаки!»

Да я тоже так думаю =)

Рекурсия и итерация в ЭВМ это близнецы-братья. Потому, что рекурсивный вызов это повтор цикла, с запоминанием предыдущего состояния с последующим возвратом к сохраненному значению. Хорошо это видно на ассемблере (только вместо call представить несколько push'ей и jmp, а вместо ret jmp к сохранённой метке)

Хорошо это видно на ассемблере (только вместо call представить несколько push'ей и jmp, а вместо ret jmp к сохранённой метке)

Да! Особенно хорошо это демонстрирует этот пример из википедии:

%% qsort:qsort(List)
%% Sort a list of items
-module(qsort).     % This is the file 'qsort.erl'
-export([qsort/1]). % A function 'qsort' with 1 parameter is exported (no type, no name)
 
qsort([]) -> []; % If the list [] is empty, return an empty list (nothing to sort)
qsort([Pivot|Rest]) ->
    % Compose recursively a list with 'Front' for all elements that should be before 'Pivot'
    % then 'Pivot' then 'Back' for all elements that should be after 'Pivot'
    qsort([Front || Front <- Rest, Front < Pivot])
    ++ [Pivot] ++
    qsort([Back || Back <- Rest, Back >= Pivot]).

И насколько помню теорию разница только в бесконечно рекурсивных функциях, которые бесполезны на компьютере.

А так, можно пройти еще более окольным путем. Рекурсию сводим к хвостовой (например, переписав через F# async). Затем хвостовую рекурсию компилируем в языке с поддержкой TCO. На уровне ассемблера хвостовые вызовы обычно превращаются в циклы (именно в циклы ассемблера, а не в циклы языка высокого уровня, как многие путают).

Для начала все рекурсии можно переделать в итерацию (даже нехвостовые).

Ценой аналогичного роста хипа.

В gcc есть -foptimize-sibling-calls для оптимизации хвостовой рекурсии. Ресурсы при этом не поедаются. Для любой другой стек переполнится через сколько-то вызовов. В нём сидят ещё аргументы функции и локальные переменные же, так что указатель будет расти далеко не на 4.

P.P.S А как в интерпретируемых языках, в той же Java?

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

Ценой аналогичного роста хипа.

За всё приходится платить. Либо память, либо мощность процессора, либо квалификация программиста. Выбор ограничен этими переменными.

Какое сильное утверждение, однако! А время запила проекта и количество багов в релизах в эти переменные, например, не входят?

тред не читал

у тя или ошибка в топике(16 вместо 32) или ты не знаеш что 32 битного хватает на 4 милиарда для беззнакового.

если же ты говориш про случай 8086 то да размер стека был ограничен сегментом который там был как раз 16 бит(65356)

ты про продолжении и благословенный J-оператор ландина?

всё равно у тя будет расти твой стек(магазиная очередь переходов) будет в твоём менеджере самописном рости.

так что ...

будет расти твой стек(магазиная очередь переходов)

Зачем очередь, если достаточно счётчика? В сложных случаях можно свести к вызову нескольких разных функций с разными счётчиками.

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

.

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

Теоретически оптимизация хвостовой рекурсии может делаться JIT какой-то конкретной реализации,

Сомневаюсь, что так можно. Так как в случае exception жабакодер будет смотреть stack trace и что он там увидит?

Так как в случае exception жабакодер будет смотреть stack trace и что он там увидит?

Ну, теоретически, он мог бы увидеть параметры первого «нерекурсивного» вызова функции и параметры последнего вызова без всей промежуточной цепочки

Сомневаюсь, что так можно.

Как минимум в айбиемовской жабке точно есть, в дотнетиненаде тоже как-то иссобачились.

Так как в случае exception жабакодер будет смотреть stack trace и что он там увидит?

Кто их ведает, этих жабакодеров.

Треду не хватает того анончика с зигохистоморфными препроморфизмами..