Подобный этому вопрос был задан пару лет назад , но этот вопрос еще сложнее.
Задача проста. Напишите программу (в вашем языке по выбору) , который многократно выполняет код без использования каких - либо повторение структур , таких как while
, for
, do while
, foreach
или goto
( Так что для всех вас nitpickers, вы не можете использовать цикл ). Однако рекурсия не допускается в смысле, вызывающем функцию (см. Определение ниже) . Это сделало бы этот вызов слишком легким.
Нет никаких ограничений на то, что должно быть выполнено в цикле, но опубликуйте объяснение с вашим ответом, чтобы другие могли точно понять, что реализуется.
Для тех, кто может зацикливаться на определениях, определение цикла для этого вопроса:
A programming language statement which allows code to be repeatedly executed.
И определение рекурсии для этого вопроса будет вашим стандартным определением рекурсивной функции:
A function that calls itself.
Победителем будет ответ, который получил наибольшее количество голосов 16 июля в 10 часов утра по восточному времени. Удачи!
ОБНОВИТЬ:
Чтобы смягчить путаницу, которая все еще выражается, это может помочь:
Правила как указано выше:
- Не используйте петли или переход
- Функции не могут называть себя
- Делай, что хочешь в «петле»
Если вы хотите реализовать что-то, а правила явно не запрещают это, сделайте это. Многие ответы уже согнули правила.
function A
вызовыfunction B
иfunction B
вызовы,function A
пока одна из функций выполняет что-то. Поскольку функция не вызывает сама себя, она должна быть действительной на основе критериев ^. ^rep(f){f();f();}
- это оператор (объявление функции - это оператор в некоторых языках), который позволяет выполнять код повторно. Это запрещено. Вы просите код для реализации цикла. Если этот код синтаксически является оператором, вы просто запретили его. Другой пример:f(b) { b(); g(b); }; g(b) { f(b); }
. Я бы сказал,f
что это рекурсивная функция (будучи взаимно рекурсивным сg
). Это запрещено?Ответы:
Рубин
демонстрация
Откашливается, печатает «Банан» 3070 раз, а также помещает «Апельсин, ты рад, что я не сказал банан?».
При этом используется смешная функциональность определения метода «точно в срок» в Ruby для определения каждого метода, который находится в алфавитном порядке между словами «ahem» и «Кроме того» («ahem», «ahen», «aheo», «ahep», «aheq», "aher", "ahes", "ahet", "aheu", "ahev" ...), чтобы сначала напечатать Banana, а затем вызвать следующий в списке.
источник
String#next
который вызывается вmethod_missing
функциях, более или менее похожих на добавление 1 к числу, за исключением того, что он работает со всеми буквенно-цифровыми символами (и не с буквенными значениями, если они являются единственными символами в строке). См. Ruby-doc.org/core-2.1.2/String.html#method-i-nextb.my_tag
. Это также используется в моделях ActiveRecord илиOpenStruct
. В «Ват-разговоре» он говорит, что глобальныйmethod_missing
- это плохо, но сфера действия - это круто.Python - 16
или любой другой язык с eval.
источник
"print 1;"
), дублирует ее 9 раз (*9
), затем выполняет результирующую строку (exec
). Повторение фрагмента кода на самом деле без зацикливания вообще.exec
кeval
илиprint
кecho
.CSharp
Я расширил код до более удобочитаемой формы, так как это больше не кодовый гольф, и добавил счетчик приращений, чтобы люди могли реально увидеть, что эта программа что-то делает.
(Не делай этого никогда, пожалуйста).
При запуске мы создаем новый экземпляр
P
класса, который, когда программа пытается выйти, вызывает GC, который вызывает финализатор, который создает новый экземплярP
класса, который при попытке очистить создает новый,P
который вызывает финализатор. ,Программа со временем умирает.
Edit: необъяснимо, это работает только около 45k раз, прежде чем умереть. Я не совсем знаю, как GC вычислил мой хитрый бесконечный цикл, но это произошло. Суть в том, что кажется, что он этого не понял, и поток был просто убит примерно через 2 секунды выполнения: https://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an -infinite-петли здесь
Edit2: если вы думаете, что это слишком похоже на рекурсию, рассмотрите мое другое решение: https://codegolf.stackexchange.com/a/33268/23300
Он использует преобразование универсальных методов, так что во время выполнения он постоянно генерирует новые методы, и каждый метод в термине вызывает новый метод. Я также избегаю использования
reference
параметров типа, так как обычно среда выполнения может совместно использовать код для этих методов. Сvalue
параметром типа среда выполнения вынуждена создавать новый метод.источник
Finalize
поэтому их иногда вызываютfinalizer
. В реальном C # вы должны использоватьIDisposable
шаблон.Befunge
Старый добрый Befunge выводит 0 (из пустого стека) почти навсегда, так как строки переворачиваются.
источник
JS
(f=function(){ console.log('hi!'); eval("("+f+")()") })()
Функция веселья!
Функция, которая создает другую функцию с тем же телом, что и она сама, а затем запускает ее.
Он будет отображать привет в конце, когда будет достигнут предел стека, и все это рухнет.
Отказ от ответственности: вы не сможете ничего сделать в своем браузере, пока не будет достигнут предел стека.
И еще один, более зло :function f(){ var tab = window.open(); tab.f = f; tab.f()}()
Он создает функцию, которая открывает окно, затем создает функцию в этом окне, которая является копией функции, и затем запускает ее.
Отказ от ответственности: если вы разрешите открытие всплывающих окон, единственный способ закончить это будет перезагрузить компьютеристочник
f
в конце вашей второй функции. Это должно быть}f()
в конце.сборка x86 / DOS
Как это устроено
источник
Ява
Прямо из XKCD
Это бесконечная игра в ловушку между родителем и ребенком!
Цель для
CHILD
установлена вPARENT
и цельPARENT
являетсяCHILD
. КогдаPARENT
вызываетAIM
, он бросает экземплярBALL
класса, и это ловится оператором catch. Затем оператор catch вызывает,PARENT.TARGET.AIM
где находится цельCHILD
.CHILD
Экземпляр делает то же самое и «бросает мяч обратно» родителю.источник
TARGET.AIM(B);
в методеAIM
является рекурсивным вызовом. Таким образом, это нарушает правило «функции не могут себя называть».Баш, 3 персонажа
yes будет многократно возвращать 'y' на консоль
Редактировать: Всем рекомендуется редактировать эту строку:
(спасибо Оливье Дюлаку)
источник
yes
- это команда bash, которая выводит слово yes до тех пор, пока оно не будет уничтожено или поток не закроется. Если он пишет на экран, он никогда не остановится, пока вы его не убьете. Это своего рода обман, так как это команда, которая в основном состоит из цикла над printf.yes
чтобы поддерживать какой-то другой цикл.yes something | xargs someaction
без рекурсии (вы можете даже добавить -n 1 к xargs, чтобы иметь только 1 «что-то» на строку и т. д.). Использование xargs открывает путь для более сложных поведений (даже тех, которые вообще не имеют ничего общего с выводом yes)yes
.C, 35 символов
Программа выполняется сама. Я не уверен, считается ли это рекурсией или нет.
источник
exec
новый процесс заменяет исходный, поэтому нет стека вызовов, который в конечном итоге будет возвращен или переполнен.exec
заменяет предыдущий процесс. Это не переполнится, либо.C (со встроенными GCC - также, кажется, работает с Clang)
Объяснение:
main()
первые звонкиframeloop(NULL)
. В этом случае используйте__builtin_return_address()
встроенный, чтобы получить адрес возврата (вmain()
), которыйframeloop()
будет возвращен. Мы возвращаем этот адрес.printf()
чтобы показать, что мы в циклеframeloop()
с обратным адресом для предыдущего звонка. Мы просматриваем в стеке текущий адрес возврата, а когда находим его, подставляем предыдущий адрес возврата.frameloop()
вызова. Но так как адрес возврата был взломан выше, мы в конечном итоге возвращаемся к точке, в которуюmain()
должен вернуться первый вызов. Таким образом, мы в конечном итоге в петле.Поиск адреса возврата в стеке, конечно, будет чище, как цикл, но я развернул несколько итераций, чтобы вообще не было циклов.
Выход:
источник
setjmp()
/longjmp()
. Они не в стандарте c, но в стандартной библиотеке . Хотя сегодня я чувствовал, что собираю стек вручную ;-)Haskell
Следующий код не содержит рекурсивной функции (даже косвенной), не имеет циклического примитива и не вызывает никакой встроенной рекурсивной функции (использует только
IO
выходные данные и привязку), однако он повторяет заданное действие идентично:Функция
extract
ничего не называй,yc
называет простоextract
иmain
называет простоyc
иputStrLn
и>>
, что не является рекурсивным.Объяснение: Хитрость заключается в рекурсивном типе данных
Strange
. Это рекурсивный тип данных, который потребляет сам себя, что, как показано в примере, допускает произвольное повторение. Во-первых, мы можем построитьextract x
, который по существу выражает самоприменениеx x
в нетипизированном лямбда-исчислении. И это позволяет построить Y комбинатор, определенный какλf.(λx.f(xx))(λx.f(xx))
.Обновление: Как предложено, я публикую вариант, который ближе к определению Y в нетипизированном лямбда-исчислении:
источник
let
привязку и определитьyc f = extract $ C $ f.extract
, посколькуlet
привязка, возможно, является языковой функцией, которая позволяет рекурсию (классическаяlet x = x in x
). Это также уменьшает некоторые символы :)yc = extract . C . (.extract)
Y
.C ++
Далее выводится обратный отсчет от 10 до «Blast off!» используя шаблонное метапрограммирование.
Это может выглядеть как классический пример рекурсии, но на самом деле это не так, по крайней мере, технически, в зависимости от вашего определения. Компилятор сгенерирует десять различных функций.
countdown<10>
печатает "T минус 10", а затем звонкиcountdown<9>
и так далее доcountdown<0>
, что печатает "Blast off!" а затем возвращается. Эта рекурсия происходит, когда вы компилируете код, но исполняемый файл не содержит никаких циклических структур.В C ++ 11 можно добиться аналогичных эффектов, используя
constexpr
ключевое слово, например, эту факториальную функцию. (Невозможно реализовать пример обратного отсчета таким образом, посколькуconstexpr
функции не могут иметь побочных эффектов, но я думаю, что это может быть возможно в следующем C ++ 14.)Опять же, это действительно выглядит рекурсию, но компилятор будет расшириться
factorial(10)
в10*9*8*7*6*5*4*3*2*1
, а затем , возможно , заменить его постоянным значением3628800
, поэтому исполняемый файл не будет содержать зацикливания или рекурсивный код.источник
3628800
непосредственного создания без промежуточная форма.constexpr
был специально разработан для того, чтобы сделать (некоторые аспекты) шаблонное метапрограммирование устаревшим, поэтому, безусловно, стоит упомянуть об этом в посте на эту тему.&countdown<N-1> != &countdown<N>
.Ява
Давайте поиграем с загрузчиком классов Java и установим его как своего родителя:
Этот цикл на самом деле настолько силен, что вам придется использовать a,
kill -9
чтобы остановить его :-)Он использует 100,1% процессора моего Mac.
Вы можете попробовать переместить
System.out
в конце основной функции, чтобы поэкспериментировать с другим забавным поведением.источник
CSharp
Еще один и такой же злой ::
Это не рекурсия ... это повторение шаблонов кода. Хотя кажется, что мы вызываем один и тот же метод, среда выполнения постоянно создает новые методы. Мы используем параметр типа int, поскольку это фактически вынуждает его создавать новый тип, и каждый экземпляр метода должен содержать новый метод. Здесь нельзя поделиться кодом. В конце концов мы убиваем стек вызовов, поскольку он бесконечно ждет возврата int, который мы обещали, но никогда не доставляли. Аналогичным образом мы продолжаем писать тип, который мы создали, чтобы сделать его интересным. По сути, каждый C, который мы вызываем, представляет собой совершенно новый метод, который имеет одно и то же тело. На самом деле это невозможно в таких языках, как C ++ или D, которые делают свои шаблоны во время компиляции. Поскольку C # JIT очень ленив, он создает эти вещи только в последний момент. Таким образом,
источник
Redcode 94 (Core War)
MOV 0, 1
Копирует инструкцию по адресу ноль в адрес один. Поскольку в Core War все адреса относятся к текущему адресу ПК и по модулю размера ядра, это бесконечный цикл в одной инструкции без перехода.
Эта программа (воин) называется « Бес » и была впервые опубликована А. К. Дьюдни.
источник
SPL 0, 0; MOV 1, -2
действительно.дротик
Я думаю, это был бы классический способ сделать рекурсию без какой-либо реальной рекурсивной функции. Ни одна функция ниже не ссылается на себя по имени, прямо или косвенно.
(Попробуйте на dartpad.dartlang.org )
источник
JS
Не очень оригинальный, но маленький. 20 символов
источник
,1
и это все еще будет работать,setInterval
это не утверждение; это только функция. Он используется внутри выражения выражения, и если мы не можем использовать выражения выражения, то я просто больше не знаю.Сигналы в С
Поведение этой программы, очевидно, очень сильно не определено, но сегодня на моем компьютере она продолжает печатать «Привет, мир!».
источник
Emacs Lisp
Это прекрасное время для демонстрации мощного дизайна Lisp, где «код - это данные, а данные - это код». Конечно, эти примеры очень неэффективны, и их никогда не следует использовать в реальном контексте.
Макросы генерируют код, который является развернутой версией предполагаемого цикла, и этот сгенерированный код является тем, что оценивается во время выполнения.
повторить-это: позволяет зацикливаться N раз
повторить тест
Повторяю-это-с индексом:
Этот макрос похож,
repeat-it
но на самом деле он работает так же, как обычный макрос цикла,do-times
он позволяет вам указать символ, который будет привязан к индексу цикла. Он использует символ времени раскрытия, чтобы гарантировать, что переменная индекса установлена правильно в начале каждого цикла, независимо от того, изменили ли вы его значение во время тела цикла.повторить тест с индексом:
Этот тест показывает, что:
Тело оценивает N раз
переменная индекса всегда устанавливается правильно в начале каждой итерации
изменение значения символа с именем «отступление» не повлияет на индекс
источник
Нетипизированное лямбда-исчисление
источник
Хаскель, 24 персонажа
или в сжатой форме, с 24 символами
(хотя текст изменен, он все равно будет зацикливаться - он будет печатать две кавычки и новую строку бесконечно)
объяснение: print "abc" - это, по сути, действие ввода-вывода, которое просто печатает "abc".
repeat - это функция, которая принимает значение x и возвращает бесконечный список, состоящий только из x.
sequence_ - это функция, которая принимает список действий ввода-вывода и возвращает действие ввода-вывода, которое выполняет все действия последовательно.
так что, в основном, эта программа создает бесконечный список команд печати «abc» и многократно выполняет их. без петель или рекурсии.
источник
repeat
что будетa programming language statement which allows code to be repeatedly executed
.fix(print"">>)
, это также не включает в себя явно названные функции повторения.ASM (x86 + I / O для Linux)
Неважно, сколько будут бороться ваши ничтожные языки высокого уровня, все равно это будет просто скрытая манипуляция указателем инструкций. В конце это будет своего рода "goto" (jmp), если вам не скучно, чтобы развернуть цикл во время выполнения.
Вы можете проверить код на Ideone
Вы также можете ознакомиться с более изысканной версией этой идеи в DOS-коде Matteo Italia .
Он начинается со строки 0..9 и заменяет ее на A..J, прямые переходы не используются (поэтому допустим, что "goto" не произошло), а также нет повторений.
Код, вероятно, может быть меньше при некотором злоупотреблении вычислением адресов, но работа над онлайн-компилятором утомительна, поэтому я оставлю все как есть.
Основная часть:
Весь код
источник
Препроцессор C
Небольшая «техника», с которой я столкнулся во время обфускации. Нет рекурсии функции, но есть ... рекурсия файла?
noloop.c:
Я написал / проверил это с помощью gcc. Очевидно, что ваш компилятор должен поддерживать
__INCLUDE_LEVEL__
макрос (или, наоборот,__COUNTER__
макрос с некоторыми изменениями) для того, чтобы это компилировалось. Должно быть достаточно очевидно, как это работает, но для удовольствия запустите препроцессор без компиляции кода (используйте-E
флаг с gcc).источник
PHP
Вот один с PHP. Циклы включаются одним и тем же файлом, пока счетчик не достигнет $ max:
Так же, как цикл for:
источник
header("Location: .?x=".$_GET['x']+1);
считаться рекурсиями?питон
Следующий код не содержит рекурсивной функции (прямой или косвенной), не имеет циклического примитива и не вызывает никакой встроенной функции (кроме
print
):Принты "Привет, мир!" определенное количество раз.
Объяснение: Функция
z
реализует строгий комбинатор с фиксированной точкой Z , который (хотя и не определен рекурсивно) позволяет выразить любой рекурсивный алгоритм.источник
g
очень косвенно рекурсивным.g
называется этот вызовg
снова? Конечно, уловка заключается в самопримененииg(g)
, но рекурсия здесь не предусмотрена. Вы бы действительно назвалиg
косвенно рекурсивным, если бы не виделиg(g)
? Это стандартный способ сделать это на языках, которые не допускают рекурсивных определений, таких как лямбда-исчисление.g
качестве аргумента,x
а затем позвонитеx(x)
.машинный код z80
В среде, где вы можете выполнять на каждом адресе и отображать ПЗУ везде, отобразите 64 КБ ПЗУ, заполненного нулями, на все адресное пространство.
Что он делает: ничего. Несколько раз.
Как это работает: процессор начнет выполнение, байт
00
- этоnop
инструкция, поэтому он просто продолжит работу, достигнет адреса$ffff
, переместится$0000
и продолжит выполнениеnop
s до тех пор, пока вы не сбросите его.Чтобы сделать это немного более интересным, заполните память другим значением (будьте осторожны, чтобы избежать инструкций потока управления).
источник
Perl-регулярное выражение
демонстрация
или попробуйте как:
(?!)
Никогда не совпадают. Таким образом, механизм регулярных выражений пытается сопоставить каждую позицию нулевой ширины в соответствующей строке.(q x x x 10)
же самое, что(" " x 10)
- повторитьspace
десять раз.Редактировать: изменил «символы» в позиции нулевой ширины, чтобы быть более точным для лучшего понимания. Смотрите ответы на этот вопрос stackoverflow .
источник
T-SQL -12
источник
GO
на самом деле это директива SSMS, поэтому вы не можете поместить ее в объекты сценариев T-SQL, например, в хранимую процедуру.C #
Распечатывает все целые числа из uint.MaxValue в 0.
источник
JS (в браузере)
Как насчет этого?
Печатает текущее время и перезагружает страницу.
источник
[Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"]