Предназначенная бесконечная рекурсия, функции без возврата - PullRequest
Новая
       4

Предназначенная бесконечная рекурсия, функции без возврата

7 голосов
/ 19 октября 2011

Бесконечная рекурсия чаще всего нежелательна, и когда это происходит, она обычно приводит к переполнению стека или ошибкам сегмента.

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

Работа в C ++ и C, где стек, как правило, увеличивается для каждого вызова функции, и каждая функция возвращает и извлекает часть стека, которую она обработала.

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

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

Помните, я на самом деле не спрашиваю, практично ли это, только если это возможно. Для науки!

Ответы [ 3 ]

15 голосов
/ 19 октября 2011

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

Это используется для tail-call-оптимизация , так что да, это возможно и используется на практике. В таких языках, как C ++, это хорошая возможность, потому что иногда алгоритмы проще выразить с помощью рекурсии, но более эффективно реализовать с помощью цикла. Преобразование может в некоторых случаях выполняться автоматически компилятором.

5 голосов
/ 19 октября 2011

Существует метод, называемый прыжками на батуте, который используется для реализации продолжения в стиле программирования без использования хвостовой оптимизации. Если вы рассматриваете любой язык без поддержки TCO, такой как JavaScript, и исследовательские решения для CPS на этом языке, то вполне вероятно, что решение включает в себя прыжки на батуте.

По сути, при прыжке на батуте есть функция, называемая батутом, которая итеративно вызывает функции, возвращающие тук.

Я знаю, что вы сказали "без первой функции, которую нужно возвращать, а затем снова запускать через цикл" - вот что такое трамплин - но учитывая, что это C ++, оставляя области, например, возврат, занимает центральное место в ядре разработка автоматического управления ресурсами C ++ с помощью деструкторов (см .: RAII). В качестве альтернативы вы можете использовать функции C setjmp() / longjmp() для очистки стека, но тогда вам нужно быть очень осторожным, чтобы убедиться, что все ресурсы высвобождены должным образом.

2 голосов
/ 20 октября 2011

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

  call FuncA
  call FuncB

Вы можете заменить его на: 

  push ReturnAddress
  push FuncB
  jmp FuncA
ReturnAddress:

Это заставляет ret в конце FuncA переходить непосредственно к FuncB, а не обратно к вызывающей стороне, а затем к FuncB. Не возможно на языках более высокого уровня.

Есть также это: 

 call FuncA
 ret

, который можно изменить на: 

 jmp FuncA
...