Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

A question similar to this has been asked a couple of years ago, but this one is even trickier.

The challenge is simple. Write a program (in your language of choice) that repeatedly executes code without using any repetition structures such as while, for, do while, foreach or goto (So for all you nitpickers, you can't use a loop). However, recursion is not allowed, in the function calling itself sense (see definition below). That would make this challenge far too easy.

There is no restriction on what needs to be executed in the loop, but post an explanation with your answer so that others can understand exactly what is being implemented.

For those who may be hung up on definitions, the definition of a loop for this question is:

A programming language statement which allows code to be repeatedly executed.

And the definition of recursion for this question will be your standard recursive function definition:

A function that calls itself.

Winner will be the answer that has the most upvotes on July 16th at 10 AM eastern time. Good luck!

UPDATE:

To calm confusion that is still being expressed this may help:

Rules as stated above:

  • Don't use loops or goto
  • Functions cannot call themselves
  • Do whatever you want in the 'loop'

If you want to implement something and the rules don't explicitly disallow it, go ahead and do it. Many answers have already bent the rules.

share|improve this question
17  
For those who want an easy trick, i can't be bothered posting it :P Just make 2 functions, function A calls function B and function B calls function A while 1 of the functions performs something. Since the function doesn't call itself it should be valid based on the criteria ^.^ –  Teun Pronk Jul 9 at 14:34
2  
"Changed to popularity contest for a focus on creativity" Changing the question is cheating! –  CousinCocaine Jul 9 at 15:12
4  
The definition of "recursion" isn't very useful. It would be better to disallow recursive functions, which are functions that refer to themselves, directly or indirectly. –  lrn Jul 10 at 5:59
3  
What is unclear is the "definitions" of loop constructor and recursion. Neither are very precise. Example: rep(f){f();f();} - this is a statement (a function declaration is a statement in some languages) that allows executing code repeatedly. Is it disallowed. You ask for code to implement a loop. If that code is syntactically a statement, you have just disallowed it. Another example: f(b) { b(); g(b); }; g(b) { f(b); }. I'd say f is a recursive function (by being mutually recursive with g). Is it disallowed? –  lrn Jul 10 at 6:08
3  
@CailinP, what I'm "hung up on" is that questions on the site should be on topic for the site: that means having a clear, objective specification, which this question does not. –  Peter Taylor Jul 11 at 10:20

111 Answers 111

up vote 202 down vote accepted

Ruby

def method_missing(meth,*args)
  puts 'Banana'
  send(meth.next)
end

def also
  puts "Orange you glad I didn't say banana?"
end

ahem

Demo

Clears its throat, prints "Banana" 3070 times, and also puts "Orange you glad I didn't say banana?".

This uses Ruby's ridiculous just-in-time method definition functionality to define every method that lies alphabetically between the words 'ahem' and 'also' ("ahem", "ahen", "aheo", "ahep", "aheq", "aher", "ahes", "ahet", "aheu", "ahev"...) to first print Banana and then call the next in the list.

share|improve this answer
2  
It eventually hits "also", which is defined, and therefore not missing. –  histocrat Jul 9 at 19:45
58  
This is hysterical. –  Michael B Jul 9 at 21:55
4  
@barrycarter: In Ruby, String#next, which is called in method_missing functions more or less like adding 1 to a number except it works with all alphanumeric characters (and non-alnums if they are the only characters in the string). See ruby-doc.org/core-2.1.2/String.html#method-i-next –  3Doubloons Jul 10 at 0:38
2  
@NickT it is usable in classes like XML builders where you can any tag created only by b.my_tag. It also is used in ActiveRecord models or OpenStruct. In 'Wat talk' he say that global method_missing is bad, but scoped is awesome. –  Łukasz Niemier Jul 10 at 7:07
2  
I remember an old comment on another ruby program: "I like it because it has meth" –  vidya sagar Jul 11 at 5:35

Python - 16

or any other language with eval.

exec"print 1;"*9
share|improve this answer
    
Can you describe what your program does? –  CailinP Jul 9 at 13:53
10  
It takes a string ("print 1;"), duplicates it 9 times(*9), then executes the resulting string(exec). Repeating a chunk of code without actually looping at all. –  scragar Jul 9 at 16:46
9  
Yay for string multiplication! –  Thane Brimhall Jul 9 at 20:37
1  
Also works in Ruby if you change the exec to eval or the print to echo. –  Ajedi32 Jul 11 at 18:05

CSharp

I've expanded the code into a more readable fashion as this is no longer code golf and added an increment counter so that people can actually see that this program does something.

class P{
    static int x=0;
    ~P(){
        System.Console.WriteLine(++x);
        new P();
    }
    static void Main(){
        new P();
    }
}

(Don't do this ever please).

On start we create a new instance of the P class, which when the program tries to exit calls the GC which calls the finalizer which creates a new instance of the P class, which when it tries to clean up creates a new P which calls the finalizer...

The program eventually dies.

Edit: Inexplicably this runs only around 45k times before dying. I don't quite know how the GC figured out my tricky infinite loop but it did. The short is it seems it didn't figure it out and the thread just was killed after around 2 seconds of execution: http://stackoverflow.com/questions/24662454/how-does-a-garbage-collector-avoid-an-infinite-loop-here

Edit2: If you think this is a little too much like recursion consider my other solution: http://codegolf.stackexchange.com/a/33268/23300

It uses reification of generic methods so that at runtime it constantly is generating new methods and each method in term calls a newly minted method. I also avoid using reference type parameters, as normally the runtime can share the code for those methods. With a value type parameter the runtime is forced to create a new method.

share|improve this answer
18  
I didn't even know C# had destructors. +1 for teaching me. –  Sieg Jul 9 at 19:48
4  
@TheRare, it does but they are non-deterministic in nature and may never be called during a program's execution. They are implemented as an override of the virtual method Finalize so they sometimes are called finalizer. In real C#, you should use the IDisposable pattern. –  Michael B Jul 9 at 20:05
    
It seems that there is a time-out that occurs at some point. I don't think it is the GC that is stopping your cycle, but instead the operating system deciding that your program is taking too long to end. –  LVBen Jul 9 at 21:38
    
I think this is really the runtime deciding to kill the program not necessarily the OS. The garbage collector thread called on program end is given a fixed time limit of ~2 seconds before it's killed. –  Michael B Jul 9 at 21:46
    
With some minor modifications (not letting the program end, releasing the the 1st P object to the GC, and repeatedly calling GC.Collect), I can get it to run indefinitely. –  LVBen Jul 9 at 21:49

Befunge

.

Good old Befunge outputs 0 (from an empty stack) pretty much forever, as lines wrap around.

share|improve this answer
    
Ha! I love tricks like this –  CailinP Jul 9 at 22:28

JS

(f=function(){ console.log('hi!'); eval("("+f+")()") })()

Function fun!

A function that creates another function with the same body as itself and then runs it.

It will display hi at the end when the stack limit is reached and the entire thing collapses.

Disclaimer: you'll not be able to do anything in your browser until stack limit is reached.


And another one, more evil:

function f(){ var tab = window.open(); tab.f = f; tab.f()}()

It creates a function which opens up a window, then creates a function within that window which is copy of the function, and then runs it.

Disclaimer: if you'll allow opening of popups the only way to finish this will be to restart your computer

share|improve this answer
5  
This is pretty evil for sure ;) –  CailinP Jul 9 at 18:52
22  
@CailinP Pretty eval for sure. –  Sieg Jul 11 at 11:44
    
I think you're missing an f at the end of your second function. It should be }f() in the end. –  Chirag64 Jul 15 at 7:36
2  
Unfortunately, I noticed it because I tried it. :P –  Chirag64 Jul 15 at 8:05
4  
-1 - this is just recursion. –  immibis Jul 17 at 9:59

x86 assembly/DOS

    org 100h

start:
    mov dx,data
    mov ah,9h
    int 21h
    push start
    ret

data:
    db "Hello World!",10,13,"$"

Did I say no reversed tail recursion? Did I? madame mim purple dragons

How it works

The ret instruction, used to return from a function, actually pops the return address from the stack (which normally is put there by the corresponding call) and jumps to it. Here at each iteration we push the entrypoint address on the stack before returning, thus generating an infinite loop.

share|improve this answer
9  
+1 for the picture, plus you did this in assembly! –  CailinP Jul 10 at 13:08
    
I was wondering if this was possible in assembly. –  Ian D. Scott Jul 10 at 17:00
2  
Mess with the stack at your peril. Here be dragons ;-) –  DigitalTrauma Jul 10 at 18:39
1  
I was going to call out codegolf.stackexchange.com/a/34295/11259 as a dup of this one, but I see that is actually the earlier answer –  DigitalTrauma Jul 10 at 18:57
    
@DigitalTrauma: yep, I noticed after I posted my entry, but I got to attached to the picture of Madame Mim. :-) Fortunately there are some differences (his is a bit more obfuscated and works on 32 bit Linux, mine is played straight on DOS and has no other jump), if no one has any objection I'd leave this here anyway. –  Matteo Italia Jul 10 at 20:36

C (with GCC builtins - also seems to work with clang)

  • No explicit loops
  • No explicit gotos
  • No recursion
  • Just good old-fashioned messing with the stack (kids, don't try this at home without supervision):
#include <stdio.h>

void *frameloop (void *ret_addr) {
    void **fp;
    void *my_ra = __builtin_return_address(0);

    if (ret_addr) {
        fp = __builtin_frame_address(0);
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        else fp++;
        if (*fp == my_ra) return (*fp = ret_addr);
        return NULL;
    } else {
        return (my_ra);
    }
}

int main (int argc, char **argv) {
    void *ret_addr;
    int i = 0;

    ret_addr = frameloop(NULL);
    printf("Hello World %d\n", i++);
    if (i < 10) {
        frameloop(ret_addr);
    }
}

Explanation:

  • main() first calls frameloop(NULL). In this case use the __builtin_return_address() builtin to get the return address (in main()) that frameloop() will return to. We return this address.
  • printf() to show we're looping
  • now we call frameloop() with the return address for the previous call. We look through the stack for the current return address, and when we find it, we substitute the previous return address.
  • We then return from the 2nd frameloop() call. But since the return address was hacked above, we end up returning to the point in main() where the first call should return to. Thus we end up in a loop.

The search for the return address in the stack would of course be cleaner as a loop, but I unrolled a few iterations for the sake of no looping whatsoever.

Output:

$ CFLAGS=-g make frameloop
cc -g    frameloop.c   -o frameloop
$ ./frameloop 
Hello World 0
Hello World 1
Hello World 2
Hello World 3
Hello World 4
Hello World 5
Hello World 6
Hello World 7
Hello World 8
Hello World 9
$ 
share|improve this answer
2  
nice! I wonder why those functions aren't part of the C spec? ;-D –  Brian Minton Jul 9 at 20:16
4  
@BrianMinton Actually a similar thing should be achievable with setjmp()/longjmp(). These aren't in the c standard, but are in the standard library. I felt like munging the stack manually today though ;-) –  DigitalTrauma Jul 9 at 20:35
    
@BrianMinton My guess is because it is in CPU specs, which makes it (hardware) platform dependent. And it is rather dangerous to use when stackframe is auto-generated, I would not be surprised if AV would cry about such code. Check this or this for x86 asm versions. –  PTwr Jul 11 at 7:01

Bash, 3 characters

yes

yes will repeatedly return 'y' to the console

Edit: Everyone is encouraged to edit this line:

yes something | xargs someaction

(thanks to Olivier Dulac)

share|improve this answer
1  
Why will this keep running? im not questioning it just trying to figure out why. –  Teun Pronk Jul 9 at 13:00
2  
@TeunPronk yes is a bash command that prints out the word yes until it's killed or the stream becomes closed. If it's writing to the screen it'll never stop until you kill it. It's kind of cheating though, since it's a command that basically consists of a loop over printf. –  scragar Jul 9 at 13:44
1  
More fun would be to use yes to keep some other loop going. –  trlkly Jul 9 at 22:38
3  
@izkata: but then you can : yes something | xargs someaction : no recursion (you can even add -n 1 to xargs to only have 1 "something" per line, etc) . Using xargs opens the way for more complex behaviours (even ones who don't have anything at all to do with the yes output) –  Olivier Dulac Jul 10 at 13:20
4  
@scragar you should have just replied yes. –  daviewales Jul 12 at 4:33

C, 35 characters

main(int a,char**v){execv(v[0],v);}

The program executes itself. I'm not sure if this is considered recursion or not.

share|improve this answer
4  
@mniip Tail recursion, then, if it applied at the process level –  Izkata Jul 10 at 2:05
3  
@Izkata Tail recursion is still recursion, but this isn't recursion. Recursion implies a function (or process in this case) 'waiting' for another iteration of itself to terminate. In this case, exec causes the new process to replace the original one, so there's no call stack that will eventually return or overflow. –  millinon Jul 10 at 2:42
3  
@millinon In a language that supports the optimization, tail recursion replaces the previous call in the call stack, similar to how exec replaces the previous process. It won't overflow, either. –  Izkata Jul 10 at 3:16
1  
@millinon just to be super pedantic and to drag out this discussion longer, in the Scheme programming language, this optimization is a language feature. It's in the spec that if you make a tail-recursive call, the interpreter/compiler has to reuse the last stack frame. This is because Scheme has no built-in looping structures, so the only way to implement a loop in Scheme is to do tail-recursion, and it would kind of suck if you got stack overflows from trying to loop too many times :) –  Ord Jul 11 at 9:53
2  
If you want pedantry, Scheme doesn't have "tail call optimisation", it has "proper tail calls". It is not an optimisation, it is a basic requirement of the language standard and failing to supply it is not permitted, so "optimisation" (or the suggestion that it has anything to do with recursion) is very much a discouraged term. –  Leushenko Jul 11 at 10:49

Java

Straight from XKCD

Bonding

It's a never-ending game of catch between a parent and child!

The target of CHILD is set to PARENT and the target of PARENT is the CHILD. When the PARENT calls AIM, it throws the instance of the BALL class and it is caught by the catch statement. The catch statement then calls PARENT.TARGET.AIM where the target is the CHILD. The CHILD instance does the same and "throws the ball back" to the parent.

share|improve this answer
2  
I like those comics! –  Derek 朕會功夫 Jul 11 at 5:59
1  
Would be better if the ball was actually being thrown between the parent and child. As-is, the ball is always thrown and caught by the same "person". –  Ajedi32 Jul 11 at 18:14
    
@Ajedi32 It would actually appear it does throw it back and forth; Parents TARGET is the child, and child's target is parent. Aim is called on parent, who throes the ball and has the child aim and throw the ball, cue loop –  Alex Coleman Jul 12 at 3:09
10  
@AlexColeman This code is analogous to the parent throwing the ball up in the air, catching it, then handing it to the child who does the same before handing the ball back to the parent, and so on. –  Ajedi32 Jul 13 at 3:21
7  
The command TARGET.AIM(B); in method AIM is a recursive call. So this violates the "functions can not call themselves" rule. –  Theodore Norvell Jul 14 at 13:36

Haskell

The following code contains no recursive function (even indirectly), no looping primitive and doesn't call any built-in recursive function (uses only IO's output and binding), yet it repeats a given action idenfinitely:

data Strange a = C (Strange a -> a)

-- Extract a value out of 'Strange'
extract :: Strange a -> a
extract (x@(C x')) = x' x

-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (extract x))
        in extract fxx

main = yc (putStrLn "Hello world" >>)

Function extract doesn't call anything, yc calls just extract and main calls just yc and putStrLn and >>, which aren't recursive.

Explanation: The trick is in the recursive data type Strange. It is a recursive data type that consumes itself, which, as shown in the example, allows arbitrary repetition. First, we can construct extract x, which essentially expresses self-application x x in the untyped lambda calculus. And this allows to construct the Y combinator defined as λf.(λx.f(xx))(λx.f(xx)).


Update: As suggested, I'm posting a variant that is closer to the definition of Y in the untyped lambda calculus:

data Strange a = C (Strange a -> a)

-- | Apply one term to another, removing the constructor.
(#) :: Strange a -> Strange a -> a
(C f) # x = f x
infixl 3 #

-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f =  C (\x -> f (x # x)) # C (\x -> f (x # x))

main = yc (putStrLn "Hello world" >>)
share|improve this answer
2  
Recursive data structures instead of recursive functions... nice. –  ValekHalfHeart Jul 11 at 0:23
4  
this one is close to my heart being someone who is interested in total functional programing. You just showed how to make the Y-combinator with a negatively recurring data type. This is why total languages require recurring types occur to the right of the arrow and why rose trees are disallowed. Nice one! I made an account here just to upvote this! –  Jake Jul 14 at 4:45
    
You could remove the let binding and define yc f = extract $ C $ f.extract, since let binding arguably a language feature that allows recursion (the classical let x = x in x). This also reduces some chars :) –  Earth Engine Jul 16 at 3:01
    
or even yc = extract . C . (.extract) –  Earth Engine Jul 16 at 3:05
    
@EarthEngine True, I just wanted to keep the structure closer to the original definition of Y. –  Petr Pudlák Jul 16 at 5:34

C++

The following outputs a countdown from 10 to "Blast off!" using template metaprogramming.

#include <iostream>

template<int N>
void countdown() {
    std::cout << "T minus " << N << std::endl;
    countdown<N-1>();
}

template<>
void countdown<0>() {
    std::cout << "Blast off!" << std::endl;
}

int main()
{
    countdown<10>();
    return 0;
}

It might look like a classic example of recursion, but it actually isn't, at least technically, depending on your definition. The compiler will generate ten different functions. countdown<10> prints "T minus 10" and then calls countdown<9>, and so on down to countdown<0>, which prints "Blast off!" and then returns. The recursion happens when you compile the code, but the executable doesn't contain any looping structures.

In C++11 one can achieve similar effects using the constexpr keyword, such as this factorial function. (It's not possible to implement the countdown example this way, since constexpr functions can't have side-effects, but I think it might be possible in the upcoming C++14.)

constexpr int factorial(int n)
{
    return n <= 1 ? 1 : (n * factorial(n-1));
}

Again this really looks like recursion, but the compiler will expand out factorial(10) into 10*9*8*7*6*5*4*3*2*1, and then probably replace it with a constant value of 3628800, so the executable will not contain any looping or recursive code.

share|improve this answer
2  
The second one of these really is pure and simple recursion, not metaprogramming. Firstly because the compiler will (in the general case) emit a regular function body for you to use with non-constant arguments; and secondly because when it does perform a compile-time operation, it doesn't do any of that template-style "expansion" stuff, it runs a standard in-place evaluation - the same as the runtime one - to produce 3628800 directly without an intermediate form. –  Leushenko Jul 11 at 11:23
    
@Leushenko yeah I know. But then again the template example example does the same thing - uses a recursive function in a Turing-complete language at compile-time - the only difference is that the constexpr one uses a language that looks much more like C++. As with all the answers this one bends the rules, and I'm just being honest about it. constexpr was specifically designed to make (some aspects of) template metaprogramming obsolete, so it definitely seems worth mentioning in a post on the subject. –  Nathaniel Jul 11 at 12:59
    
+1: &countdown<N-1> != &countdown<N>. –  Thomas Eding Jul 18 at 7:33

CSharp

One more and equally wicked::

public class P{

    class A<B>{
        public static int C<T>(){
            System.Console.WriteLine(typeof(T));
            return C<A<T>>();
        }
    }
    public static void Main(){
        A<P>.C<int>();
    }
}

This is not recursion... this is reification of code templates. While it appears we are calling the same method, the runtime is constantly creating new methods. We use the type parameter of int, as this actually forces it to create an entire new type and each instance of the method has to jit a new method. It cannot code share here. Eventually, we kill the call stack as it waits infinitely for the return of int that we promised but never delivered. In a similar fashion, we keep writing the type we created to keep it interesting. Basically each C we call is an enitrely new method that just has the same body. This is not really possible in a language like C++ or D that do their templates at compile time. Since, C# JIT is super lazy it only creates this stuff at the last possible moment. Thus, this is another fun way to get csharp to keep calling the same code over and over and over...

share|improve this answer

Java

Let's play with Java class loader and set it as its own parent:

import java.lang.reflect.Field;

public class Loop {
    public static void main(String[] args) throws Exception {
        System.out.println("Let's loop");
        Field field = ClassLoader.class.getDeclaredField("parent");
        field.setAccessible(true);
        field.set(Loop.class.getClassLoader(), Loop.class.getClassLoader());

    }
}

This loop is actually so strong you'll have to use a kill -9 to stop it :-)

It uses 100,1% of my Mac's CPU.

100,1% of CPU

You can try to move the System.out at the end of the main function to experiment an alternate funny behavior.

share|improve this answer
4  
+1 for turning the cpu up to 11 –  kbsou Jul 10 at 14:34
    
lol. getting java stuck in itself :) –  masterX244 Jul 12 at 21:29
    
Love the JVM recursive loading hack. –  impinball Jul 13 at 7:32

Dart

I guess this would be the classical way of doing recursion without any actual recursive function. No function below refers to itself by name, directly or indirectly.

(Try it at try.dartlang.org)

// Strict fixpoint operator.
fix(f) => ((x)=>f(x(x))) ((x)=>(v)=>f(x(x))(v));
// Repeat action while it returns true.
void repeat(action) { fix((rep1) => (b) { if (b()) rep1(b); })(action); }

main() {
  int x = 0;
  repeat(() {  
    print(++x);
    return x < 10;
  });
}
share|improve this answer
4  
The Y combinator? –  aditsu Jul 9 at 17:53
3  
Technically, I guess it's the Z combinator because it's for a strict language. The Y combinator requires a lazy language to avoid infinite unfolding. The only difference is that the latter part of it is eta-expanded. –  lrn Jul 10 at 5:56

Haskell, 24 characters

sequence_ (repeat (print "abc"))

or in a condensed form, with 24 characters

sequence_$repeat$print"" 

(although the text is changed, this will still loop - this will print two quotes and a newline infinitely)

explanation: print "abc" is basically an i/o action that just prints "abc".
repeat is a function which takes a value x and returns an infinite list made of only x.
sequence_ is a function that takes a list of i/o actions and returns an i/o action that does all of the actions sequentially.

so, basically, this program makes an infinite list of print "abc" commands, and repeatedly executes them. with no loops or recursion.

share|improve this answer
4  
I was going to post basically the same answer in Clojure, but I thought repeat would be a programming language statement which allows code to be repeatedly executed. –  Sieg Jul 9 at 16:04
3  
fix(print"">>), this also involves no explicitly named repetition functions. –  mniip Jul 9 at 16:47
1  
@TheRare I don't know how is is in closure, but in Haskell repeat isn't "a programming language statement which allows code to be repeatedly executed" - it is a function that generates infinite lists. it's a loop just as "int[] arr = {x,x,x};" is a loop. –  proud haskeller Jul 9 at 17:54
1  
yes, but something must be implemented using recursion, because without it it's basically impossible –  proud haskeller Jul 10 at 19:23
3  
Actually, every function there is in this code is defined using recursion - even print –  proud haskeller Jul 10 at 19:27

JS

Not very original but small. 20 chars.

setInterval(alert,1)
share|improve this answer
    
You can actually remove ,1 and it will still works, –  Derek 朕會功夫 Jul 11 at 5:59
    
@Derek朕會功夫 if I do that, I only get one alert on Firefox –  xem Jul 11 at 8:22
1  
In chrome it works without the last parameter. The code should be counted as valid if it works in at least one environment. –  Derek 朕會功夫 Jul 11 at 15:55
3  
@Derek朕會功夫 setInterval is not a statement, though; it's only a function. It's used inside an expression statement, and if we can't use expression statements, then I just don't even know anymore. –  Cory Jul 11 at 21:17
1  
@Cory - Well I guess that's valid then! –  Derek 朕會功夫 Jul 12 at 0:55

Emacs Lisp

This is a great time to show off Lisp's powerful design where "code is data and data is code". Granted, these examples are very inefficient and this should never be used in a real context.

The macros generate code that is an unrolled version of the supposed loop and that generated code is what is evaluated at runtime.

repeat-it: allows you to loop N times

(defmacro repeat-it (n &rest body)
  "Evaluate BODY N number of times.
Returns the result of the last evaluation of the last expression in BODY."
  (declare (indent defun))
  (cons 'progn (make-list n (cons 'progn body))))

repeat-it test:

;; repeat-it test
(progn
  (setq foobar 1)

  (repeat-it 10
    (setq foobar (1+ foobar)))

  ;; assert that we incremented foobar n times
  (assert (= foobar 11)))

repeat-it-with-index:

This macro is like repeat-it but it actually works just like the common looping macro do-times it allows you to specify a symbol that will be bound to the loop index. It uses an expansion time symbol to ensure that the index variable is set correctly at the beginning of each loop regardless of whether or not you modify it's value during the loop body.

(defmacro repeat-it-with-index (var-and-n &rest body)
  "Evaluate BODY N number of times with VAR bound to successive integers from 0 inclusive to n exclusive..
VAR-AND-N should be in the form (VAR N).
Returns the result of the last evaluation of the last expression in BODY."
  (declare (indent defun))
  (let ((fallback-sym (make-symbol "fallback")))
    `(let ((,(first var-and-n) 0)
           (,fallback-sym 0))
       ,(cons 'progn
              (make-list (second var-and-n)
                         `(progn
                            (setq ,(first var-and-n) ,fallback-sym)
                            ,@body
                            (incf ,fallback-sym)))))))

repeat-it-with-index test:

This test shows that:

  1. The body does evaluate N times

  2. the index variable is always set correctly at the beginning of each iteration

  3. changing the value of a symbol named "fallback" won't mess with the index

;; repeat-it-with-index test
(progn
  ;; first expected index is 0
  (setq expected-index 0)

  ;; start repeating
  (repeat-it-with-index (index 50)
    ;; change the value of a  'fallback' symbol
    (setq fallback (random 10000))
    ;; assert that index is set correctly, and that the changes to
    ;; fallback has no affect on its value
    (assert (= index expected-index))
    ;; change the value of index
    (setq index (+ 100 (random 1000)))
    ;; assert that it has changed
    (assert (not (= index expected-index)))
    ;; increment the expected value
    (incf expected-index))

  ;; assert that the final expected value is n
  (assert (= expected-index 50)))
share|improve this answer

Redcode 94 (Core War)

MOV 0, 1

Copies instruction at address zero to address one. Because in Core War all addresses are relative to current PC address and modulo the size of the core, this is an infinite loop in one, non-jump, instruction.

This program (warrior) is called "Imp" and was first published by AK Dewdney.

share|improve this answer
1  
Imps shall march, ready your gates, ready them or you'll be crushed. –  Sieg Jul 10 at 22:54
    
Ready your SPL 0, 0; MOV 1, -2 indeed. –  wberry Jul 13 at 21:42

PHP

Here's one with PHP. Loops by including the same file until counter reaches $max:

<?php
if (!isset($i))
    $i = 0;        // Initialize $i with 0
$max = 10;         // Target value

// Loop body here
echo "Iteration $i <br>\n";

$i++;               // Increase $i by one on every iteration

if ($i == $max)
    die('done');    // When $i reaches $max, end the script
include(__FILE__);  // Proceed with the loop
?>

The same as a for-loop:

<?php
for ($i = 0; $i < 10; $i++) {
    echo "Iteration $i <br>\n";
}
die('done');
?>
share|improve this answer
    
Darn, this counts as recursion as well, doesn't it? –  Pichan Jul 9 at 22:40
    
Don't think it is - the similarity comes to mind of @Nathaniel's example: the preprocessor will include these files which are then evaluated simultaneously. –  eithedog Jul 10 at 9:36
    
@Pichan I would say it is more of loop unfolding, as you end with copies of code in memory. –  PTwr Jul 11 at 7:04
    
I just saw the question today and came up with almost identical code. Too late for me! –  TecBrat Jul 15 at 14:47

Python

The following code contains no recursive function (directly or indirect), no looping primitive and doesn't call any built-in function (except print):

def z(f):
    g = lambda x: lambda w: f(lambda v: (x(x))(v), w)
    return g(g)

if __name__ == "__main__":
    def msg(rec, n):
        if (n > 0):
            print "Hello world!"
            rec(n - 1)
    z(msg)(7)

Prints "Hello world!" a given number of times.

Explanation: Function z implements the strict Z fixed-point combinator, which (while not recursively defined) allows to express any recursive algorithm.

share|improve this answer
    
I would call g very much indirectly recursive. –  Sieg Jul 10 at 16:11
    
@TheRare Why? What is your argument? What does g call that calls g again? Of course that the trick is the self-application g(g), but there is no recursion involved. Would you indeed call g indirectly recursive if you haven't seen g(g)? This is the standard way how to do it in languages that don't allow recursive definitions, such as the lambda calculus. –  Petr Pudlák Jul 10 at 16:46
    
You give g as argument x and then call x(x). –  Sieg Jul 10 at 16:49
1  
@TheRare A function (or a set of functions) isn't recursive or non-recursive by how it's used, this is determined just by its definition. –  Petr Pudlák Jul 10 at 17:05
1  
all of the answers cheat in one way or another: there's always recursion or a loop somewhere, if not in the answer, then in code the answer invokes. I like the way this one cheats. –  Wayne Conrad Jul 11 at 14:47

ASM (x86 + I/O for Linux)

It does not matter how much your puny high level languages will struggle, it will still be just hidden instruction pointer manipulation. In the end it will be some sort of "goto" (jmp), unless you are bored enough to unroll loop in runtime.

You can test code on Ideone

You can also check out more refined version of this idea in Matteo Italia DOS code.

It starts with string of 0..9 and replaces it with A..J, no direct jumps used (so lets say that no "goto" happened), no recurrence either.

Code probably could be smaller with some abuse of address calculation, but working on online compiler is bothersome so I will leave it as it is.

Core part:

mov dl, 'A' ; I refuse to explain this line!
mov ebx, msg ; output array (string)

call rawr   ; lets put address of "rawr" line on stack
rawr: pop eax ; and to variable with it! In same time we are breaking "ret"

add eax, 4 ; pop eax takes 4 bytes of memory, so for sake of stack lets skip it
mov [ebx], dl ; write letter
inc dl ; and proceed to next 
inc ebx
cmp dl, 'J' ; if we are done, simulate return/break by leaving this dangerous area
jg print

push eax ; and now lets abuse "ret" by making "call" by hand
ret

Whole code

section     .text
global      _start                              

_start:

;<core>
mov dl, 'A'
mov ebx, msg

call rawr
rawr: pop eax

add eax, 4
mov [ebx], dl
inc dl
inc ebx
cmp dl, 'J'
jg print

push eax
ret
;</core>

; just some Console.Write()
print:
    mov     edx,len
    mov     ecx,msg
    mov     ebx,1
    mov     eax,4
    int     0x80

    mov     eax,1
    xor     ebx, ebx
    int     0x80

section     .data

msg     db  '0123456789',0xa
len     equ $ - msg
share|improve this answer
    
I was going to call this out as a dup of codegolf.stackexchange.com/a/34298/11259, but I see this is the earlier answer. +1 –  DigitalTrauma Jul 10 at 18:56
    
@DigitalTrauma oh, I see someone made refined version of my idea - old trick, but in era of managed code people tend to forgot how things truly work. (I dislike golfing, way too often it is reduced to "look mom! I can make stuff happen by pressing one key!") –  PTwr Jul 10 at 20:45

Signals in C

#include <stdio.h>
#include <signal.h>

int main(void) {
    signal(SIGSEGV, main);
    *(int*)printf("Hello, world!\n") = 0;
    return 0;
}

The behaviour of this program is obviously very much undefined, but today, on my computer, it keeps printing "Hello, world!".

share|improve this answer

Untyped lambda calculus

λf.(λx.f (x x)) (λx.f (x x))
share|improve this answer
3  
I'm not sure if this counts as recursion or not, what with being the fundamental theoretical basis for it... +1 anyway. –  fluffy Jul 12 at 18:17

T-SQL -12

print 1
GO 9

Actually more of a quirk of Sql Server Management Studio. GO is a script separator and is not part of the T-SQL language. If you specify GO followed by a number it will execute the block that many times.

share|improve this answer
1  
I use T-SQL almost everyday and had no idea that you could do this with GO. +1 –  CailinP Jul 11 at 0:32
    
Technically, that's not T-SQL. GO is actually an SSMS directive, which is why you cannot put it in T-SQL scripted objects, like say a stored procedure. –  RBarryYoung Jul 21 at 12:54
    
Yeah, I added that in my spoiler comment. I would figure using sqlcmd would be too much cheating. –  Michael B Jul 21 at 14:53

C#

Prints out all integers from uint.MaxValue to 0.

   class Program
   {
      public static void Main()
      {
          uint max = uint.MaxValue;
          SuperWriteLine(ref max);
          Console.WriteLine(0);
      }

      static void SuperWriteLine(ref uint num)
      {
          if ((num & (1 << 31)) > 0) { WriteLine32(ref num); }
          if ((num & (1 << 30)) > 0) { WriteLine31(ref num); }
          if ((num & (1 << 29)) > 0) { WriteLine30(ref num); }
          if ((num & (1 << 28)) > 0) { WriteLine29(ref num); }
          if ((num & (1 << 27)) > 0) { WriteLine28(ref num); }
          if ((num & (1 << 26)) > 0) { WriteLine27(ref num); }
          if ((num & (1 << 25)) > 0) { WriteLine26(ref num); }
          if ((num & (1 << 24)) > 0) { WriteLine25(ref num); }
          if ((num & (1 << 23)) > 0) { WriteLine24(ref num); }
          if ((num & (1 << 22)) > 0) { WriteLine23(ref num); }
          if ((num & (1 << 21)) > 0) { WriteLine22(ref num); }
          if ((num & (1 << 20)) > 0) { WriteLine21(ref num); }
          if ((num & (1 << 19)) > 0) { WriteLine20(ref num); }
          if ((num & (1 << 18)) > 0) { WriteLine19(ref num); }
          if ((num & (1 << 17)) > 0) { WriteLine18(ref num); }
          if ((num & (1 << 16)) > 0) { WriteLine17(ref num); }
          if ((num & (1 << 15)) > 0) { WriteLine16(ref num); }
          if ((num & (1 << 14)) > 0) { WriteLine15(ref num); }
          if ((num & (1 << 13)) > 0) { WriteLine14(ref num); }
          if ((num & (1 << 12)) > 0) { WriteLine13(ref num); }
          if ((num & (1 << 11)) > 0) { WriteLine12(ref num); }
          if ((num & (1 << 10)) > 0) { WriteLine11(ref num); }
          if ((num & (1 << 9)) > 0) { WriteLine10(ref num); }
          if ((num & (1 << 8)) > 0) { WriteLine09(ref num); }
          if ((num & (1 << 7)) > 0) { WriteLine08(ref num); }
          if ((num & (1 << 6)) > 0) { WriteLine07(ref num); }
          if ((num & (1 << 5)) > 0) { WriteLine06(ref num); }
          if ((num & (1 << 4)) > 0) { WriteLine05(ref num); }
          if ((num & (1 << 3)) > 0) { WriteLine04(ref num); }
          if ((num & (1 << 2)) > 0) { WriteLine03(ref num); }
          if ((num & (1 <<  1)) > 0) { WriteLine02(ref num); }
          if ((num & (1 <<  0)) > 0) { WriteLine01(ref num); }
      }

      private static void WriteLine32(ref uint num) { WriteLine31(ref num); WriteLine31(ref num); }
      private static void WriteLine31(ref uint num) { WriteLine30(ref num); WriteLine30(ref num); }
      private static void WriteLine30(ref uint num) { WriteLine29(ref num); WriteLine29(ref num); }
      private static void WriteLine29(ref uint num) { WriteLine28(ref num); WriteLine28(ref num); }
      private static void WriteLine28(ref uint num) { WriteLine27(ref num); WriteLine27(ref num); }
      private static void WriteLine27(ref uint num) { WriteLine26(ref num); WriteLine26(ref num); }
      private static void WriteLine26(ref uint num) { WriteLine25(ref num); WriteLine25(ref num); }
      private static void WriteLine25(ref uint num) { WriteLine24(ref num); WriteLine24(ref num); }
      private static void WriteLine24(ref uint num) { WriteLine23(ref num); WriteLine23(ref num); }
      private static void WriteLine23(ref uint num) { WriteLine22(ref num); WriteLine22(ref num); }
      private static void WriteLine22(ref uint num) { WriteLine21(ref num); WriteLine21(ref num); }
      private static void WriteLine21(ref uint num) { WriteLine20(ref num); WriteLine20(ref num); }
      private static void WriteLine20(ref uint num) { WriteLine19(ref num); WriteLine19(ref num); }
      private static void WriteLine19(ref uint num) { WriteLine18(ref num); WriteLine18(ref num); }
      private static void WriteLine18(ref uint num) { WriteLine17(ref num); WriteLine17(ref num); }
      private static void WriteLine17(ref uint num) { WriteLine16(ref num); WriteLine16(ref num); }
      private static void WriteLine16(ref uint num) { WriteLine15(ref num); WriteLine15(ref num); }
      private static void WriteLine15(ref uint num) { WriteLine14(ref num); WriteLine14(ref num); }
      private static void WriteLine14(ref uint num) { WriteLine13(ref num); WriteLine13(ref num); }
      private static void WriteLine13(ref uint num) { WriteLine12(ref num); WriteLine12(ref num); }
      private static void WriteLine12(ref uint num) { WriteLine11(ref num); WriteLine11(ref num); }
      private static void WriteLine11(ref uint num) { WriteLine10(ref num); WriteLine10(ref num); }
      private static void WriteLine10(ref uint num) { WriteLine09(ref num); WriteLine09(ref num); }
      private static void WriteLine09(ref uint num) { WriteLine08(ref num); WriteLine08(ref num); }
      private static void WriteLine08(ref uint num) { WriteLine07(ref num); WriteLine07(ref num); }
      private static void WriteLine07(ref uint num) { WriteLine06(ref num); WriteLine06(ref num); }
      private static void WriteLine06(ref uint num) { WriteLine05(ref num); WriteLine05(ref num); }
      private static void WriteLine05(ref uint num) { WriteLine04(ref num); WriteLine04(ref num); }
      private static void WriteLine04(ref uint num) { WriteLine03(ref num); WriteLine03(ref num); }
      private static void WriteLine03(ref uint num) { WriteLine02(ref num); WriteLine02(ref num); }
      private static void WriteLine02(ref uint num) { WriteLine01(ref num); WriteLine01(ref num); }
      private static void WriteLine01(ref uint num) { Console.WriteLine(num--); }
   }
share|improve this answer
    
I don't really know if this counts. You are explicitly calling WriteLine01 Int.MaxValue times. It just exploded behind a massive amount of callstack. –  Michael B Jul 9 at 20:57
    
How does it not count? There is no loop and no recursion. –  LVBen Jul 9 at 21:00
1  
Also, the call stack is not anywhere near massive unless maybe you consider a 32 calls high to be massive. –  LVBen Jul 9 at 21:02
1  
Why only 32 times instead of 4294967296 times? –  LVBen Jul 12 at 19:53
3  
@ja72 If I'm ever working on an open source project in which I cannot use loops or recursion, then I am totally going to contribute code like this! –  LVBen Jul 13 at 0:28

C Preprocessor

A little "technique" that I came up with during an obfuscation challenge. There's no function recursion, but there is... file recursion?

noloop.c:

#if __INCLUDE_LEVEL__ == 0
int main() 
{
    puts("There is no loop...");
#endif
#if __INCLUDE_LEVEL__ <= 16
    puts(".. but Im in ur loop!");
    #include "noloop.c"
#else
    return 0;
}
#endif
share|improve this answer

JS (in browser)

How about this?

document.write(new Date());
location = location;

Prints the current time and reloads the page.

share|improve this answer
    
Oh shoot. I just posted an answer with the same basic concept. I had been scanning the page for "JavaScript" or anything showing HTML tags. I suppose I might leave my answer up, just because it handles the corner-case where the location contains a "#". Anyway, +1. –  Cory Jul 11 at 21:36
    
In Firefox 30: [Exception... "The operation is insecure." code: "18" nsresult: "0x80530012 (SecurityError)" location: "<unknown>"] –  Alex Reynolds Jul 20 at 11:48
    
@AlexReynolds Huh, weird. Mine works just fine on FF 30. –  Pichan Jul 21 at 0:07
    
I only copied and pasted in your code as it was written. It doesn't work. Perhaps you have some special security preferences enabled to make this work? –  Alex Reynolds Jul 21 at 4:52
    
@AlexReynolds Nope, never changed any security settings. And it works on Chrome too. –  Pichan Jul 24 at 20:33

z80 machine code

In an environment where you can execute at every address and map ROM everywhere, map 64kb of ROM filled with zeroes to the entire address space.

What it does: nothing. Repeatedly.

How it works: the processor will start executing, the byte 00 is a nop instruction, so it will just continue on, reach the address $ffff, wrap around to $0000, and continue executing nops until you reset it.

To make it do slightly more interesting, fill the memory with some other value (be careful to avoid control flow instructions).

share|improve this answer
    
You could fill the memory with zeroes, and place a real program in there somewhere. –  Sieg Jul 12 at 10:23
    
So you could put in a 64k program, with no branching whatsoever, and it would just repeatedly execute? –  Bill Woodger Jul 12 at 12:26
    
@BillWoodger you could, especially if you have no interrupts on the platform (or none enabled) –  harold Jul 12 at 12:59
    
Kind of fun :-) –  Bill Woodger Jul 12 at 14:31

Perl-regex

(q x x x 10) =~ /(?{ print "hello\n" })(?!)/;

demo

or try it as:

perl -e '(q x x x 10) =~ /(?{ print "hello\n" })(?!)/;'

The (?!) never match. So the regex engine tries to match each zero width positions in the matched string.

The (q x x x 10) is the same as (" " x 10) - repeat the space ten times.

Edit: changed the "characters" to zero width positions to be more precise for better understandability. See answers to this stackoverflow question.

share|improve this answer

protected by Doorknob Jul 15 at 12:51

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.